(algorithm)
Definition: Compute the greatest common divisor of two integers, u and v, expressed in binary. The run time complexity is O((log2 u v)²) bit operations.
See also Euclid's algorithm.
Note:
Discovered by J. Stein in 1967. Another source says discovered by R. Silver and J. Tersian in 1962 and published by G. Stein in 1967. The algorithm uses the following observations.
Here is the algorithm. It is especially efficient for operations on binary representations.
Algorithm B in [Knuth97, vol. 2, Sect. 4.5.2]. Torsten Eichstädt suggested incrementing g in step 2.3 (g++) and returning v left shifted g times in step 4 (return v<<g). 4 April 2006. Alex Peyser pointed out that g must start at 0. 10 July 2008.
Author: PEB
Binary Euclid's Algorithm including examples and references.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 20 November 2008.
HTML page formatted Wed Feb 4 11:02:21 2009.
Cite this as:
Paul E. Black, "binary GCD", in
Dictionary of Algorithms and Data
Structures [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 20 November 2008. (accessed TODAY)
Available from: http://www.itl.nist.gov/div897/sqg/dads/HTML/binaryGCD.html