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

DOI10.1016/J.AIM.2015.12.008MaRDI QIDQ908058zbMATH OpenOpenAlexFDO

Authors Ian D. Morris

Publication date 2 February 2016

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

analysis of algorithmsEuclidean algorithmrandom dynamical systemtransfer operatorgreatest common divisor

Mathematics Subject Classification ID

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

Abstract: The binary Euclidean algorithm is a modification of the classical Euclidean algorithm for computation of greatest common divisors which avoids ordinary integer division in favour of division by powers of two only. The expectation of the number of steps taken by the binary Euclidean algorithm when applied to pairs of integers of bounded size was first investigated by R. P. Brent in 1976 via a heuristic model of the algorithm as a random dynamical system. Based on numerical investigations of the expectation of the associated Ruelle transfer operator, Brent obtained a conjectural asymptotic expression for the mean number of steps performed by the algorithm when processing pairs of odd integers whose size is bounded by a large integer. In 1998 B. Vall'ee modified Brent's model via an induction scheme to rigorously prove an asymptotic formula for the average number of steps performed by the algorithm; however, the relationship of this result with Brent's heuristics remains conjectural. In this article we establish previously conjectural properties of Brent's transfer operator, showing directly that it possesses a spectral gap and preserves a unique continuous density. This density is shown to extend holomorphically to the complex right half-plane and to have a logarithmic singularity at zero. By combining these results with methods from classical analytic number theory we prove the correctness of three conjectured formulae for the expected number of steps, resolving several open questions promoted by D. E. Knuth in The Art of Computer Programming.

Recommendations

• scientific article; zbMATH DE number 1186933
• On the asymptotic analysis of the Euclidean algorithm
• Dynamics of the binary Euclidean algorithm: Functional analysis and operators
• scientific article; zbMATH DE number 3581610
• Existence of a limiting distribution for the binary GCD algorithm

Cites work

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

Cited in

(4)

• scientific article; zbMATH DE number 1186933 (Why is no real title available?)
• The random continued fraction transformation
• Asymptotic counting in conformal dynamical systems
• Existence of a limiting distribution for the binary GCD algorithm

This page was built for publication: A rigorous version of R. P. Brent's model for the binary Euclidean algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q908058)