## Twenty years' analysis of the binary Euclidean algorithm

183. R. P. Brent,
Twenty years' analysis of the binary Euclidean algorithm,
* Millenial Perspectives in Computer Science:
Proceedings of the 1999 Oxford-Microsoft Symposium in honour of
Professor Sir Antony
Hoare*
(edited by J. Davies, A. W. Roscoe and J. Woodcock),
Palgrave, New York, 2000, 41-53.
Also (extended version):
* Further analysis of the Binary Euclidean algorithm*,
Technical Report PRG TR-7-99, Oxford University Computing Laboratory,
November 1999, 18 pp.
arXiv:1303.2772v1

Paper:
dvi (19K),
pdf (199K)
ps (69K).

Technical Report:
dvi (30K),
pdf (217K),
ps (110K).

Overhead transparencies from the Hoare Symposium:

dvi (1 per page, 16K),
pdf (4 per page, 222K),
ps (4 per page, 126K).

## Abstract

The binary Euclidean algorithm is a variant of the classical
Euclidean algorithm. It avoids divisions and multiplications, except by powers
of two, so is potentially faster than the classical algorithm
on a binary machine.
We describe the binary algorithm and consider its average case behaviour.
In particular,
we correct some small but interesting errors in the literature
[37],
discuss some recent results of Vallée, and describe a numerical
computation which confirms a conjecture of Vallée
to (at least) 40 decimal places.

## Comments

The numerical computations were performed using the
MP package.
Related papers are
[ 37,
77,
79,
82,
96].

Go to next publication

Return to Richard Brent's index page