Dynamics of the Binary Euclidean Algorithm: Functional Analysis and Operators

We provide here a complete average--case analysis of the binary continued fraction of a random rational with numerator and denominator odd and less than $N$. We analyse the three main parameters of the binary continued fraction expansion that are the height, the number of steps of the Binary Euclidean algorithm, and finally the sum of the exponents of powers of 2 contained in the numerators of the binary continued fraction. The average values of these parameters are shown to be asymptotic to $A_i \log N$, and the three constants $A_i$ are related to the invariant measure of the Perron-Frobenius operator linked to this dynamical system. The Binary Euclidean algorithm has been previously studied in 1976 by Brent who provided a partial analysis based on a heuristic model and some unproven conjecture. He analysed only the second parameter, i.e. the number of steps of the algorithm. Our methods are quite different, proven without any heuristic hypothesis or conjecture, and more general, since they allow to study all the parameters of the binary continued fraction expansion.