Euclidean algorithms are Gaussian
Copyright policy )Euclidean algorithms are Gaussian
This study provides new results about the probabilistic behaviour of a class of Euclidean algorithms: the asymptotic distribution of a whole class of cost-parameters associated to these algorithms is normal. For the cost corresponding to the number of steps Hensley already has proved a Local Limit Theorem; we give a new proof, and extend his result to other euclidean algorithms and to a large class of digit costs, obtaining a faster, optimal, rate of convergence. The paper is based on the dynamical systems methodology, and the main tool is the transfer operator. In particular, we use recent results of Dolgopyat.
fourth revised version - 2 figures - the strict convexity condition used has been clarified
FOS: Computer and information sciences, Algebra and Number Theory, Functional analytic techniques in dynamical systems; zeta functions, (Ruelle-Frobenius) transfer operators, etc., Probabilistic analysis of algorithms, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Central limit theorem, Central limit and other weak theorems, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Transfer operator, Computational Complexity (cs.CC), Computer Science - Computational Complexity, Dynamical systems, Local limit theorem, Computer Science - Data Structures and Algorithms, Perron's formula, Relations of ergodic theory with number theory and harmonic analysis, Analysis of algorithms, Data Structures and Algorithms (cs.DS), Dirichlet series, F.2.1, I.1.2, Number-theoretic algorithms; complexity
FOS: Computer and information sciences, Algebra and Number Theory, Functional analytic techniques in dynamical systems; zeta functions, (Ruelle-Frobenius) transfer operators, etc., Probabilistic analysis of algorithms, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Central limit theorem, Central limit and other weak theorems, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Transfer operator, Computational Complexity (cs.CC), Computer Science - Computational Complexity, Dynamical systems, Local limit theorem, Computer Science - Data Structures and Algorithms, Perron's formula, Relations of ergodic theory with number theory and harmonic analysis, Analysis of algorithms, Data Structures and Algorithms (cs.DS), Dirichlet series, F.2.1, I.1.2, Number-theoretic algorithms; complexity
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).57 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!