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)
Nearby terms:
Euclid « Euclidean Algorithm « Euclidean norm «
Euclid's Algorithm » Eudora » EULA » EULER
|
