Euclidean algorithm (Scala)

From LiteratePrograms

Other implementations: C | Erlang | Forth | Haskell | Java | Java, recursive | OCaml | Prolog | Python | Scala | Standard ML

The Euclidean algorithm is an efficient method for computing the greatest common divisor of two natural numbers (or polynomials, or any other object with the necessary structure), and was one of the first known algorithms to be described formally. It is based on the two identities:

a > b implies: gcd(a, b) = gcd(b, a mod b)

gcd(a, 0) = a

The gcd method requires that a and b are positive integers but doesn't require that a > b.

<<gcd method>>=
def gcd(a: Long, b: Long): Long = (a, b) match {
    trivial case
    reversed case
    base case
    general case
}

The trivial case applies when a is equal to b:

<<trivial case>>=
case (a, `a`)        => a

The reversed case applies when b > a:

<<reversed case>>=
case (a, b) if b > a => gcd(b, a)

The base case applies when b is equal to 0:

<<base case>>=
case (a, 0)          => a

Since a > b now holds, the first identity can be used for the general case:

<<general case>>=
case _               => gcd(b, a % b)

Sample code and demonstration

Here's some code demonstrating how to use the above method:

<<Euclid.scala>>=
object Euclid {
    gcd method
    def main(args: Array[String]) {
        val a = args(0).toLong
        val b = args(1).toLong
        println(gcd(a, b))
    }
}

If we compile and run the following command lines:

scala Euclid 35 42
scala Euclid 35 40
scala Euclid 35 38

We get the following outputs:

7
5
1

Download code