A rigorous version of R. P. Brent's model for the binary Euclidean algorithm

DOI10.1016/j.aim.2015.12.008zbMath1391.11005arXiv1409.0729OpenAlexW2963862333MaRDI QIDQ908058

Ian D. Morris

Publication date: 2 February 2016

Published in: Advances in Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1409.0729

zbMATH Keywords

greatest common divisoranalysis of algorithmsEuclidean algorithmtransfer operatorrandom dynamical system

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Number-theoretic algorithms; complexity (11Y16) Functional analytic techniques in dynamical systems; zeta functions, (Ruelle-Frobenius) transfer operators, etc. (37C30) Multiplicative structure; Euclidean algorithm; greatest common divisors (11A05) Random dynamical systems (37H99) Evaluation of number-theoretic constants (11Y60)

Related Items

The random continued fraction transformation, Asymptotic Counting in Conformal Dynamical Systems

Cites Work

• A note on ``Euclidean algorithms are Gaussian by V. Baladi and B. Vallée
• Existence of a limiting distribution for the binary GCD algorithm
• Dynamics of the binary Euclidean algorithm: Functional analysis and operators
• Composition operators and classical function theory
• Origins of the analysis of the Euclidean algorithm
• Asymptotic auto-correlation for closed geodesics
• Dynamical analysis of a class of Euclidean algorithms.
• On a problem raised by Gabriel and Beurling
• Euclidean algorithms are Gaussian
• Perturbation theory for linear operators.
• Decay of correlations
• A supplement to J. Shallit's paper ``Origins of the analysis of the Euclidean algorithm
• Gaussian laws for the main parameters of the Euclid algorithms
• Euclidean dynamics
• Computational problems associated with Racah algebra
• Semigroups of operators and measures of noncompactness
• An Introduction to Operators on the Hardy-Hilbert Space
• Distribution of Lévy constants for quadratic numbers
• On a theorem of Heilbronn
• Comparison theorems and orbit counting in hyperbolic geometry
• Dynamical Analysis of the Parametrized Lehmer–Euclid Algorithm
• Sur un Theoreme Spectral et son Application aux Noyaux Lipchitziens
• A Simple Estimate for the Number of Steps in the Euclidean Algorithm
• Généralisation du théorème de Ikehara
• The number of steps in the Euclidean algorithm
• The radius of the essential spectrum
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item