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).
We describe the binary algorithm and consider its average case behaviour. In particular, we correct some small but interesting errors in the literature , 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.
Related papers are [ 37, 77, 79, 82, 96].
Go to next publication
Return to Richard Brent's index page