GCD
I was working on a new problem from the Euler Project - they post new problems every week-ish. I decided to try this one in Erlang, to give myself more exposure to the language to see what I think of it. I realized that something was missing, and actually, I think it is missing from most languages: GCD.
Alex Stepanov has given many talks about the importance of GCD - I think there are a few four hour talks out there that have been recorded and are very interesting to watch. I realize more and more how right he is about this. (His paper on GCD is linked to at Stepanov Papers, which I have linked to on the right - some great reading on that site.)
It seems to be a useful function, one that should be built in. Given that it is not, I’ve included one in this blog post. Code like this should only be written once, programmers should be able to focus on the problem at hand, not worry about missing common functions - it takes away from focus. Sure, everyone could write their own, but the same is true for sin, cos, etc. GCD should be a standard, it is in J the programming language.
Before I wrote this, I did some searching, and found that a few people had written a GCD and posted their code. It was after looking at their code that I decided to open a dialog about this, since some of the ones I found were wrong, or longer, or more complex than the actual GCD calculation.
-Edward
gcd(M, 0) -> M;
gcd(M, N) -> gcd(N, M rem N).
April 14th, 2008 at 8:49 am
For completeness, here is the F# version I wrote:
let rec gcd m n =
if n = 0 then m
else gcd n (m % n)