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