GCD in F#

Now we will write a function to calculate the greatest common divisor of two numbers. The Euclidean Algorithm is an efficient, and ancient, method of finding the GCD.

Euclid's algorithm takes advantage of some properties of the gcd function and the modulus function. Here is a loose explanation of why the algorithm works

gcd(a,b) = gcd(b, a - q*b) for any integer q
a % b = a - q*b from some integer q,
so gcd(a,b) = gcd(b, a % b)

Then, we just stop the algorithm when b is zero. And now for the F# code.

let rec gcd a b =
    if b = 0 then a
    else
        gcd b (a % b)

Aside from the syntax, and checking for the end condition, this looks like the math.

And now, a few tests.

let f a b = 
    printfn "gcd(%d,%d) = %d" a b (gcd a b)
f 10 9
f (13*61*2*2*2*3) (13*2*3*5*7)
f -10 12345

With the output,

gcd(10,9) = 1
gcd(19032,2730) = 78
gcd(-10,12345) = 5

ideone.com/hHN7j