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

DOI10.1016/J.AIM.2015.12.008zbMATH Open1391.11005arXiv1409.0729OpenAlexW2963862333MaRDI QIDQ908058FDOQ908058

Authors: Ian D. Morris 

Publication date: 2 February 2016

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

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.

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

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

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)

Cites Work

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

Cited In (4)

• Title not available (Why is that?)
• 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)