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

Go to next lecture

Return to list of special lectures on algorithms