Euclid's algorithm

(algorithm)

Definition: An algorithm to compute the greatest common divisor of two positive integers. It is Euclid(a,b){if (b=0) then return a; else return Euclid(b, a mod b);}. The run time complexity is O((log a)(log b)) bit operations.

Also known as Euclidean algorithm.

Note: After [CLR90, page 810].

Author: PEB

Implementation

Worst-case behavior annotated for real time (WOOP/ADA), (Scheme).

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.

Entry modified 14 May 2007.
HTML page formatted Tue Dec 6 16:16:32 2011.

Cite this as:
Paul E. Black, "Euclid's algorithm", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 14 May 2007. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/euclidalgo.html