Analysis of the binary Euclidean algorithm

37. R. P. Brent, Analysis of the binary Euclidean algorithm, in New Directions and Recent Results in Algorithms and Complexity (edited by J. F. Traub), Academic Press, New York, 1976, 321-355. MR 54#14417, 55#11701.

Abstract: dvi (5K), pdf (109K).

Paper: pdf (1211K).

Abstract

The classical Euclidean algorithm for finding the greatest common divisor of two positive integers has been exhaustively analyzed since the time of Gauss. The theory of binary Euclidean algorithms is less well developed. We analyze the "right-shift" binary Euclidean algorithm. In particular, we show that the expected number of iterations for uniformly distributed inputs in {1, 2, 3, ... , N} is asymptotic to K log2N as N -> infinity, where K = 0.70597124610...

We introduce another binary Euclidean algorithm, the "left-shift" algorithm, and consider its expected behaviour on random inputs. The expected number of iterations for the left-shift algorithm is slightly greater than for the right-shift algorithm, but the left-shift algorithm is worth considering for use on a computer with a "normalize" instruction, as then the left-shifting loop may be replaced by a single instruction. Either of the binary algorithms could be implemented in hardware (or microcode) with approximately the same expense as integer division.

Comments

Binary Euclidean algorithms were later applied by Brent, Kung, Luk and Bojanczyk to give linear-time systolic algorithms for integer GCD computation: see [ 77, 79, 82, 96]. The polynomial GCD problem [73] is simpler because of the lack of carries.

The probabilistic assumptions of the paper were justified by Vallée (1998): see Brent [183] for a summary and references.

The existence and uniqueness of a limiting distribution (conjectured in the paper) has been proved by Gerard Maze, J. Discrete Algorithms 5 (2007), 176-186; see also http://www.arxiv.org/abs/math.GM/0504426 (21 April 2005).

Further progress has been made by Ian Morris, Advances in Mathematics 290 (26 Feb. 2016), 73-143 (preprint at http://arxiv.org/abs/1409.0729, 2 Sept 2014). In particular, Morris shows the existence of a spectral gap and a unique continuous density for the transfer operator. He deduces three conjectured formulae for the expected number of steps, resolving several open questions.

Errata

Page 326, last line: in the definition of D0(x), "D0(x) = 0" should be replaced by "D0(x) = 1". [Correction made in the online version.]

Page 342, equation (6.3): In equation (6.3) on page 342, "x" in the denominator of the last term should be replaced by "1". [Correction made in the online version.]

Some of the results are incorrect. For example, (3.1), (3.29), (3.34), and (3.35) are wrong, though a close approximation to the truth. [Corrections not made in the online version.]

Further details are given in [183]. See also Section 4.5.2 of Knuth, The Art of Computer Programming, Volume 2, third edition, 1997.

Go to next publication

Return to Richard Brent's index page