Gaussian laws for the main parameters of the Euclid algorithms

DOI10.1007/s00453-007-9009-6zbMath1142.11085OpenAlexW1993445859WikidataQ115149031 ScholiaQ115149031MaRDI QIDQ2482727

Brigitte Vallée, Loïck Lhote

Publication date: 23 April 2008

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9009-6

zbMATH Keywords

Dynamical systemsTauberian theoremsPerron's formulaAnalysis of algorithmsAverage-case analysisTransfer operatorAsymptotic Gaussian lawsDistributional analysisDynamical analysis of algorithmsEuclid's algorithms

Mathematics Subject Classification ID

Asymptotic distribution theory in statistics (62E20) Analysis of algorithms (68W40) Number-theoretic algorithms; complexity (11Y16)

Related Items (8)

Average-case complexity of the Euclidean algorithm with a fixed polynomial over a finite field ⋮ The Brun gcd algorithm in high dimensions is almost always subtractive ⋮ Numeration and discrete dynamical systems ⋮ Probabilistic analyses of the plain multiple gcd algorithm ⋮ A rigorous version of R. P. Brent's model for the binary Euclidean algorithm ⋮ Fine costs for Euclid's algorithm on polynomials and Farey maps ⋮ Analysis of generalized continued fraction algorithms over polynomials ⋮ Regularity of the Euclid algorithm; application to the analysis of fast GCD algorithms

Cites Work

• Regularity of the Euclid algorithm; application to the analysis of fast GCD algorithms
• On decay of correlations in Anosov flows
• Dynamical analysis of a class of Euclidean algorithms.
• On continued fraction expansions in positive characteristic: equivalence relations and some metric properties
• Euclidean algorithms are Gaussian
• Euclidean dynamics
• Some metrical theorems in number theory. II. - Errata
• Sharp Estimates for the Main Parameters of the Euclid Algorithm
• The exact length of the Euclidean algorithm in [ X ]
• Opérateurs de Ruelle-Mayer généralisés et analyse en moyenne des algorithmes d'Euclide et de Gauss
• Dynamical Analysis of the Parametrized Lehmer–Euclid Algorithm
• The statistics of continued fractions for polynomials over a finite field
• Euclid's Algorithm for Large Numbers
• Généralisation du théorème de Ikehara
• The number of steps in the Euclidean algorithm
• The number of steps in the Euclidean algorithm
• Digits and continuants in Euclidean algorithms. Ergodic versus Tauberian theorems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Gaussian laws for the main parameters of the Euclid algorithms