5

In this post we’re going to implement calculation of Greatest Common Divisor GCD in Clojure using Euclidean algorithm for two and more numbers.

GCD of two numbers

The algorithm is simple and boils down to taking the last non-zero reminder from a series of divisions a mod b, where b becomes a, and the reminder becomes b. This simple code explains everything: 

(defn euclid-for-two
  "Calculate GCD of given two numbers using Euclidean algorithm."
  [a b]
  (if (zero? b)
    (Math/abs a)
    (recur b (rem a b))))

GCD of more than two numbers

The above code can be easily extended to calculate GCD of many numbers. We just need to calculate GCD of the first two, then GCD of this GCD and the next number, and so on: 

(defn euclid
  "Calculate GCD of given numbers using Euclidean algorithm."
  [a b & others]
  (cond
    (and (zero? b) (nil? others)) (Math/abs a)
    (zero? b) (recur a (first others) (next others))
    :else (recur b (rem a b) others)))

Unit tests for verification

(deftest should-calculate-gcd-using-euclidean-algorithm
  (is (= 42 (euclid 0 42)))
  (is (= 120 (euclid 1080 1920)))
  (is (= 120 (euclid 1920 1080)))
  (is (= 3 (euclid 21 -9)))
  (is (= 3 (euclid -21 9)))
  (is (= 3 (euclid -6 12 9)))
  (is (= 1 (euclid 5 8 13))))

References:

Share with the World!