euclidean algorithm

from The Free On-line Dictionary of Computing (8 July 2008)
Euclid's Algorithm
Euclidean 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)