Un théorème de la limite locale pour des algorithmes Euclidiens
A local limit theorem with speed of convergence for euclidean algorithms and diophantine costs
For large , we consider the ordinary continued fraction of =/ with 1≤≤≤, or, equivalently, Euclid’s gcd algorithm for two integers 1≤≤≤, putting the uniform distribution on the set of and s. We study the distribution of the total cost of execution of the algorithm for an additive cost function on the set ℤ of possible digits, asymptotically for →∞. If is nonlattice and satisfies mild growth conditions, the local limit theorem was proved previously by the second named author. Introducing...
Page 1