LECTURE 5
Revisiting the binary Euclidean algorithm
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. In this lecture I will describe the classical and binary algorithms,
and compare their worst case and average case behaviour. In particular,
I will correct some small but significant errors in the literature,
discuss some recent results of Brigitte Vallée, and describe a numerical
computation which verifies a conjecture of Vallée
to more than 40 decimal places.
Related lecture
An earlier version of this lecture,
Revisiting the binary Euclidean algorithm,
was presented recently at Warwick University.
Bibliography
- R. P. Brent,
Analysis of the binary Euclidean algorithm,
in Algorithms and Complexity (editor J. F. Traub)
Academic Press, New York, 1976, 321-355.
Warning: this paper has some errors which will be discussed in
the lecture.
-
P. Flajolet and
R. Sedgewick,
The Average Case Analysis of Algorithms:
Mellin Transform Asymptotics,
Report 2956, INRIA, August 1996.
(Chapter 7 of a book, Analytic Combinatorics, in preparation.)
-
D. E. Knuth,
The Art of Computer Programming,
Volume 2: Seminumerical Algorithms (third edition).
Addison-Wesley, Menlo Park, 1997.
Make sure it is the third edition!
-
B. Vallée,
The complete analysis of the Binary Euclidean Algorithm,
Lecture Notes in Computer Science, Volume 1423,
Springer-Verlag, 1998, 77-94.
Go to next lecture
Return to list of special lectures on algorithms