Regularity of the Euclid algorithm; application to the analysis of fast GCD algorithms

DOI10.1016/j.jsc.2008.04.018zbMath1179.11049OpenAlexW2006804687MaRDI QIDQ1025385

Véronique Maume-Deschamps, Benoît Daireaux, Julien Clément, Brigitte Vallée, Loïck Lhote, Eda Cesaratto

Publication date: 18 June 2009

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jsc.2008.04.018

zbMATH Keywords

analysis of algorithmsfast multiplicationtransfer operatorsPerron formuladivide and conquer algorithmsEuclid algorithm

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)

Related Items

A note on ``Euclidean algorithms are Gaussian by V. Baladi and B. Vallée ⋮ Numeration and discrete dynamical systems ⋮ Gaussian laws for the main parameters of the Euclid algorithms

Uses Software

• CALYPSO

Cites Work

• On decay of correlations in Anosov flows
• On convergence rates in the central limit theorems for combinatorial structures
• Dynamics of the continued fraction map and the spectral theory of \(\text{SL}(2,\mathbb{Z})\)
• Dynamical analysis of a class of Euclidean algorithms.
• Euclidean algorithms are Gaussian
• A double-digit Lehmer-Euclid algorithm for finding the GCD of long integers
• Gaussian laws for the main parameters of the Euclid algorithms
• Euclidean dynamics
• Fast computation of continued fraction expansions.
• The thermodynamic formalism approach to Selberg’s zeta function for 𝑃𝑆𝐿(2,𝐙)
• Sharp Estimates for the Main Parameters of the Euclid Algorithm
• Dynamical Analysis of the Parametrized Lehmer–Euclid Algorithm
• Exponential decay of correlations for surface semi-flows without finite Markov partitions
• On Schönhage's algorithm and subquadratic integer gcd computation
• Algorithmic Number Theory
• Euclid's Algorithm for Large Numbers
• The number of steps in the Euclidean algorithm
• The number of steps in the Euclidean algorithm
• Digits and continuants in Euclidean algorithms. Ergodic versus Tauberian theorems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item