## 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 (1196K).

## 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* log_{2}*N* 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 recently by Ian Morris, paper to appear in
*Advances in Mathematics*
(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 D_{0}(x),
"D_{0}(x) = 0" should be replaced by
"D_{0}(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