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).


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.


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