EPI 5.10 - Greatest common divisor

Problem ¶

Design an algorithm for computing the GCD of two numbers without using multiplication, division or the modulus operator.

Solution ¶

The GCD of two numbers can be computed by recursively subtracting the smaller number from the larger until one of the numbers is 0, at which point the non-zero value is the GCD.

However this can be improved by “quickly” eliminating factors of two (by inspecting the least significant bits) and doubling and halving values (via left and right shifting by 1 respectively).

 1greatest_common_divisor x 0 = x
 2greatest_common_divisor 0 y = y
 3greatest_common_divisor x y
 4    | x_is_even && y_is_even = 2 * greatest_common_divisor (x `shiftR` 1) (y `shiftR` 1)
 5    | x_is_odd && y_is_even = greatest_common_divisor x (y `shiftR` 1)
 6    | x_is_even && y_is_odd = greatest_common_divisor (x `shiftR` 1) y
 7    | x  y = greatest_common_divisor (x - y) x
 8    | otherwise = x
 9    where
10        x_is_even = (x .&. 1) == 0
11        y_is_even = (y .&. 1) == 0
12        x_is_odd = not x_is_even
13        y_is_odd = not y_is_even