Java Programming Tutorials

Java programming tutorials with many code examples!

GCD in Clojure using Euclidean algorithm

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!
  • Steve Miner

    I suggest that you use different arities to handle the variadic args. Also, `reduce` is good for this sort of thing. The type hints will give you better performance.

    (defn euc2
    ([^long a ^long b]
    (if (zero? b)
    (Math/abs a)
    (recur b (rem a b))))
    ([a b & others] (reduce euc2 (euc2 a b) others)))

    • Thank you for the suggestions. I really like your solution with “reduce”. :-)

  • You could make the code snippets interactive with klipse. What d u think?

    • I’ll look at it. My only concern is that it would decrease page load speed, which is quite important factor.

      • It decreases page load speed just a bit. Give it a try and you ll see by yourself.
        And it adds a lot of value for the readers. They can play with your code!