Computer Dictionary Online

Medical Dictionary   Law Dictionary   Legal Dictionary   Website Design

0  1  2  3  4  5  6  7  8  9  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 


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)


Contact the Computer Dictionary Online  ::  Link to the Computer Dictionary Online  ::  Disclaimer for Computer Dictionary Online

Computer Dictionary Online
Copyright © 2017