Euclid's GCD (and LCM) algorithm

GCD
The greatest common divisor (GCD) of two integers, not both zero, is the largest integer that divides both of them. It is convenient to set GCD(0,0)=0. Basic identities concerning the GCD:

 GCD(A,B)=GCD(B,A) GCD(A,B)=GCD(-A,B) GCD(A,0)=ABS(A)

Hence we can assume that A and B are nonnegative integers.

ALGORITHM
Euclid's algorithm is described in the Elements of Euclid (circa 300 B. C. E.). It is based on the following recursion theorem:

GCD(A,B)=GCD(B,A//B)

IMPLEMENTATION
Unit: recursive internal function, external function without procedure statement

Parameters: nonnegative integer A, nonnegative integer B

Returns: GCD(A, B)

 GCD: procedure parse arg A, B if B = 0 then return A   else return GCD(B, A // B)

That program use "tail recursion". It can always be transformed to iteration by replacing function calls by assignment and do while loop statements. See Technique: Recursion Elimination.

 GCD: procedure parse arg A, B do while B > 0   parse value(B A//B) with A B end return A

The worst case of Euclid's algorithm occurs when A and B are consecutive Fibonacci numbers. The number of // operations will never exceed

FORMAT(4.8*LN(B)/LN10(),,0)

LCM
There is a related idea - the least common multiple LCM of two integer A and B. It is defined to be the smallest positive integer which is a multiple of both A and B.

ALGORITHM
Equation A*B=GCD(A,B)*LCM(A,B) reduces the calculation of LCM to the calculation of GCD.

 LCM: procedure parse arg A, B return A * B / GCD(A, B)

CONNECTIONS

Literature
Knuth D. E., Seminumerical Algorithms, vol. 2 of The Art of Computer Programming