Open Collections

The transfer operator for the binary Euclidean algorithm

Banff International Research Station for Mathematical Innovation and Discovery

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.

Mathematics; Dynamical systems and ergodic theory; Probability theory and stochastic processes; Dynamical systems

video/mp4

Author affiliation: University of Surrey

2019-05-30

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/70412

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/