BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

The transfer operator for the binary Euclidean algorithm Morris, Ian


The binary Euclidean algorithm is a modification of the classical Euclidean al- gorithm which replaces division by an arbitrary integer with division by powers of two only. Statistical properties of the classical Euclidean algorithm â such as the average number of steps required to process a pair of integers both of which are less than N â can be studied via the thermodynamic formalism of the Gauss map acting on the unit interval. To investigate similar properties for the binary Euclidean algorithm one must instead study the thermodynamic for- malism of an IID random dynamical system on the interval. I will describe a recent result on the transfer operator of the binary Euclidean algorithm which can be applied to resolve conjectures of R.P. Brent, B. Valle à e and D.E. Knuth.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International