99 Clojure Problems – 32: Determine the Greatest Common Divisor of Two Positive Integer Numbers

Use Euclid's algorithm.

Example:

(deftest p32-euclids-algorithm
  (is (= 9 (gcd 36 63)))
  (is (= 21 (gcd 462 1071)))
  (is (= 1  (gcd 1 1))))

Solution:

The greatest common divisor of two positive integers is the largest integer that divides them both without a remainder. A common form of Euclid's algorithm uses division and comparison. We start with a pair of numbers (here represented by the two arguments of the function). We then form a new pair consisting of the smaller of the two numbers and the remainder of dividing the larger number by the smaller one. We continue this process until the remainder is zero. The first number of the pair is then the greatest common divisor.

A simple recursive solution pretty much follows this description. We compare the second argument with zero to determine the exit condition. If we find it to be zero we return the first argument. Otherwise we recursively call the function itself with the second argument in the first argument's place and the remainder of the division in the second place.

The use of recursion can cause problems as the available stack size is not knowable and depends on runtime configuration. While Lamé's Theorem states that the number of steps in Euclid's algorithm never exceed five times the number of digits in the smaller number, this doesn't guarantee that we won't run out of stack frames given Clojure's support for integer sizes exceeding 64 bits. Using recur here makes the function "stack-safe."

If you look at the description of the algorithm above you will notice the implicit assumption that the first number is always the larger of the two. But we don't enforce the order of arguments (it could be done easily using Clojure's support for preconditions) because the first iteration of the algorithm will simply reorder them. This becomes clear when we make the first couple of substitutions explicit:

(gcd 36 63)
(gcd 63 (rem 36 63))
(gcd 63 36)

Read more about this series.