ALCOMFT-TR-03-14

Viviane Baladi and Brigitte Vallée
Euclidean Algorithms are Gaussian
INRIA. Work package 4. July 2003.

Abstract: This study provides new results about the probabilistic behaviour of a class of Euclidean algorithms. It proves that the asymptotic distribution of a whole class of parameters associated to these algorithms is normal. Furthermore, it precisely compares the expected properties of continued fraction expansions of real numbers and rational numbers. This paper also focuses on the basic parameter of the algorithms, the number of steps. Hensley already proved that there exists a Local Limit Theorem for this parameter, in the case of the standard Euclidean algorithm. This paper provides a new proof of this fact, both more natural and more concise, and, at the same time, an extension to two other Euclidan algorithms. The whole paper is based on the so-called dynamical analysis methodology, that views an algorithm as a dynamical system and introduces tools that come from dynamical systems into analysis of algorithms. The tranfer operator of the underlying dynamical system then plays a fundamental r\^ole, together with various other tools: Dirichlet series, Perron's formula, the Quasi-Powers theorem, saddle point method. Furthermore, this work introduces, for the first time, a new facet in dynamical analysis, distributional dynamical analysis, and it need s precise estimates on the transfer operators when the parameter varies along vertical complex lines. Such estimates are provided by adapting to the Euclidean context powerful methods due to Dolgopyat.

Postscript file: ALCOMFT-TR-03-14.ps.gz (219 kb).