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


cover contents index main page

last modified 8th August 2001
Copyright 2000-2001 Vladimir Zabrodsky
Czech Republic.

mail