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

**See also**
*binary GCD*, *extended Euclid's algorithm*, *Ferguson-Forcade 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