Regularity of the Euclid algorithm; application to the analysis of fast GCD algorithms
From MaRDI portal
Publication:1025385
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
analysis of algorithmsfast multiplicationtransfer operatorsPerron formuladivide and conquer algorithmsEuclid algorithm
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
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
