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

DOI10.1016/j.aim.2015.12.008zbMath1391.11005arXiv1409.0729MaRDI 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 divisor; analysis of algorithms; Euclidean algorithm; transfer operator; random dynamical system

Mathematics Subject Classification ID

68W40: Analysis of algorithms

11Y16: Number-theoretic algorithms; complexity

37C30: Functional analytic techniques in dynamical systems; zeta functions, (Ruelle-Frobenius) transfer operators, etc.

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

37H99: Random dynamical systems

11Y60: Evaluation of number-theoretic constants

Related Items

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

Cites Work

• 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
• 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