Tuesday, March 15, 2016

Euclid's Algorithm in Java and Scala

Euclid's algorithm (a.k.a. Euclidean algorithm) is an efficient way of finding the greatest common divisor (gcd) of two numbers - the largest positive integer that divides both numbers without a remainder. For example gcd(27, 18) = 9, gcd(15, 18) = 3, gcd(32, 64) = 32, gcd(13, 29) = 1. This algorithm is very old (about 300 BC) and well-known, so I won't describe it yet another time. Wikipedia has a great article about the subject. Euclid's algorithm pops up in my programming practice from time to time, so I decided to create this post in order to keep several implementations under my finger-tips :)

Euclid's Algorithm in Java

Java version is very easy and straightforward. One temporary variable, one easy loop and that's it. Here is the source code with a trivial client to test the implementation:
public class Main {
    static int gcd(int a, int b) {
        while (b != 0) {
            final int t = a % b;
            a = b;
            b = t;

        return a;

    public static void main(final String[] args) {
        System.out.println(gcd(27, 18));
        System.out.println(gcd(13, 29));
        System.out.println(gcd(32, 64));

Euclid's Algorithm in Scala

Scala is a great multi-paradigm programming language with lots of features, rich standard library and other goodies. Scala performs tail call optimization which allows for Euclid's algorithm to become a one-liner without additional memory costs typical for recursive algorithms:
import scala.annotation.tailrec

object Main {
  def gcd(a: Int, b: Int): Int =
    if (b == 0) a else gcd(b, a % b)

  def main(args: Array[String]): Unit = {
    println(gcd(27, 18))
    println(gcd(13, 29))
    println(gcd(32, 64))
Annotation @tailrec is not strictly necessary. It tells the Scala compiler to generate an error in the case when tail call optimization is not possible. In other words it increases programmer's level of confidence that function is actually tail-recursive and runs without additional memory costs.

No comments:

Post a Comment