Skip to content

Yet another programming solutions log

Sample bits from programming for the future generations.

Technologies Technologies
  • Algorithms and Data Structures
  • Java Tutorials
  • JUnit Tutorial
  • MongoDB Tutorial
  • Quartz Scheduler Tutorial
  • Spock Framework Tutorial
  • Spring Framework
  • Bash Tutorial
  • Clojure Tutorial
  • Design Patterns
  • Developer’s Tools
  • Productivity
  • About
Expand Search Form

GCD in Clojure using Euclidean algorithm

farenda 2017-01-01 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:

  • The code is available at GitHub
  • GCD in Java
Share with the World!
Categories Clojure Tags algorithms
Previous: GCD in Java using Euclidean Algorithm
Next: Single Responsibility Principle explained

Recent Posts

  • Java 8 Date Time concepts
  • Maven dependency to local JAR
  • Caesar cipher in Java
  • Java casting trick
  • Java 8 flatMap practical example
  • Linked List – remove element
  • Linked List – insert element at position
  • Linked List add element at the end
  • Create Java Streams
  • Floyd Cycle detection in Java

Pages

  • About Farenda
  • Algorithms and Data Structures
  • Bash Tutorial
  • Bean Validation Tutorial
  • Clojure Tutorial
  • Design Patterns
  • Java 8 Streams and Lambda Expressions Tutorial
  • Java Basics Tutorial
  • Java Collections Tutorial
  • Java Concurrency Tutorial
  • Java IO Tutorial
  • Java Tutorials
  • Java Util Tutorial
  • Java XML Tutorial
  • JUnit Tutorial
  • MongoDB Tutorial
  • Quartz Scheduler Tutorial
  • Software Developer’s Tools
  • Spock Framework Tutorial
  • Spring Framework

Tags

algorithms bash bean-validation books clojure design-patterns embedmongo exercises git gof gradle groovy hateoas hsqldb i18n java java-basics java-collections java-concurrency java-io java-lang java-time java-util java-xml java8 java8-files junit linux lists log4j logging maven mongodb performance quartz refactoring regex rest slf4j solid spring spring-boot spring-core sql unit-tests

Yet another programming solutions log © 2021

sponsored