Euclid's Algorithm

algorithm (Or "Euclidean Algorithm") An algorithm for

finding the greatest common divisor (GCD) of two numbers.

It relies on the identity

gcd(a, b) = gcd(a-b, b)

To find the GCD of two numbers by this algorithm, repeatedly

replace the larger by subtracting the smaller from it until

the two numbers are equal. E.g. 132, 168 -@# 132, 36 -@# 96, 36

-@# 60, 36 -@# 24, 36 -@# 24, 12 -@# 12, 12 so the GCD of 132 and

168 is 12.

This algorithm requires only subtraction and comparison

operations but can take a number of steps proportional to the

difference between the initial numbers (e.g. gcd(1, 1001) will

take 1000 steps).

(1997-06-30)