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
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 Addison-Wesley, 1973
Cormen T. H., Leiserson Ch. E., Rivest R. L. Introduction to Algorithms The MIT Press, Cambridge, 1990
|
