The number of steps in the Euclidean algorithm

DOI10.1006/jnth.1994.1088zbMath0811.11055MaRDI QIDQ5906618

Doug Hensley

Publication date: 11 December 1994

Published in: Journal of Number Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jnth.1994.1088

zbMATH Keywords

normal distribution; Euclidean algorithm

Mathematics Subject Classification ID

11K55: Metric theory of other algorithms and expansions; measure and Hausdorff dimension

11A05: Multiplicative structure; Euclidean algorithm; greatest common divisors

Related Items

Digits and continuants in Euclidean algorithms. Ergodic versus Tauberian theorems, New normality constructions for continued fraction expansions, A local limit theorem with speed of convergence for Euclidean algorithms and Diophantine costs, A note on ``Euclidean algorithms are Gaussian by V. Baladi and B. Vallée, Probabilistic analyses of the plain multiple gcd algorithm, A rigorous version of R. P. Brent's model for the binary Euclidean algorithm, Estimate for dispersion of lengths of continued fractions, On Gauss-Kuz'min statistics for finite continued fractions, Regularity of the Euclid algorithm; application to the analysis of fast GCD algorithms, Continued fraction algorithms, functional operators, and structure constants, The rate of convergence of approximations of a continued fraction, Dynamical analysis of a class of Euclidean algorithms., Euclidean algorithms are Gaussian, Fine costs for Euclid's algorithm on polynomials and Farey maps, Gaussian laws for the main parameters of the Euclid algorithms