Euclidean algorithm (OCaml)

From LiteratePrograms

Jump to: navigation, search
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 Euclidean algorithm is straightforward to describe in OCaml, using a function that recurses on the remainder of the division of a by b until that remainder is 0. 

let rec gcd a = function
   0 -> a
 | b -> gcd b (a mod b)

Performing the Euclidean algorithm on an arbitrary list of integers is also relatively straight-forward using the above function. Note that 0 is an identity for gcd. 

let gcd_list = List.fold_left gcd 0
Download code
Retrieved from "http://literateprograms.org/Euclidean_algorithm_%28OCaml%29"
Views