By Letter: Non-alphabet | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z
  Email this page to a friend


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).



< Previous Terms Terms Containing Euclid's Algorithm Next Terms >
ETSI
ETX
Euclid
Euclidean Algorithm
Euclidean norm
Euclidean Algorithm
greatest common divisor
Eudora
EULA
EULER
EuLisp
EUnet Ltd.


Web Standards & Support:

Link to and support eLook.org Powered by LoadedWeb Web Hosting
Valid XHTML 1.0!Valid CSS!eLook.org FireFox Extensions