The transfer operator for the binary Euclidean algorithm

Ian Morris (University of Surrey)

Frank Adams Room 1, Alan Turing Building,

The binary Euclidean algorithm is a variation of the classical Euclidean algorithm for the computation of greatest common divisors which replaces division by an arbitrary natural number with division by powers of two only. Just as the classical Euclidean algorithm may be studied by embedding it in the Gauss map on the unit interval, the binary Euclidean algorithm may be modelled by a random dynamical system on the interval which is expanding on average. We prove spectral gap results for the transfer operator associated to this random dynamical system and deduce mean running-time results for the binary Euclidean algorithm which were conjectured by D. E. Knuth in The Art of Computer Programming.

Import this event to your Outlook calendar
▲ Up to the top