Programming Research Group
Technical Report TR-7-99
Further Analysis of the Binary Euclidean Algorithm
Richard P Brent
November 1999 18pp.
Abstract
The binary Euclidean algorithm is a variant of the classical Euclidean
algorithm. It avoids multiplications and divisions, 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 errors in the literature,
discuss some recent results of Vallée, and describe a numerical
computation which supports a conjecture of Vallée.
This paper is available as a 111,394 byte
gzipped PostScript file.