Dynamical analysis of a class of Euclidean algorithms.

DOI10.1016/S0304-3975(02)00652-7zbMath1044.68164MaRDI QIDQ1401315

Brigitte Vallée

Publication date: 17 August 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

Dynamical systemsEuclidean algorithmsAnalysis of algorithmsFunctional analysisAverage-case complexityTransfer operators

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Related Items

Timed Symbolic Dynamics, Limit laws for rational continued fractions and value distribution of quantum modular forms, Statistical distribution of the Stern sequence, Bias in the number of steps in the Euclidean algorithm and a conjecture of Ito on Dedekind sums, Small quotients in Euclidean algorithms, A rigorous version of R. P. Brent's model for the binary Euclidean algorithm, Perron-Frobenius operators and the Klein-Gordon equation, Fine costs for Euclid's algorithm on polynomials and Farey maps, The dynamics of Pythagorean Triples, The mean number of steps in the Euclidean algorithm with odd partial quotients, Gaussian laws for the main parameters of the Euclid algorithms, Digits and continuants in Euclidean algorithms. Ergodic versus Tauberian theorems, Euclidean algorithms are Gaussian, Regularity of the Euclid algorithm; application to the analysis of fast GCD algorithms, Distribution of periodic points of certain Gauss shifts with infinite invariant measure, Distribution of the reduced quadratic irrationals arising from the odd continued fraction expansion

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
• Unnamed Item
• On the worst case of three algorithms for computing the Jacobi symbol
• Probabilistic encryption
• Continued fraction algorithms, functional operators, and structure constants
• Invariant measures for Markov maps of the interval
• Spectral properties of certain composition operators arising in statistical mechanics
• Maps of intervals with indifferent fixed points: thermodynamic formalism and phase transitions
• Dynamics of continued fractions with periodic constraints
• Dynamics of the binary Euclidean algorithm: Functional analysis and operators
• Composition operators and classical function theory
• Origins of the analysis of the Euclidean algorithm
• A billiard in the hyperbolic plane with decay of correlation of type \(n^{-2}\)
• The theta group and the continued fraction expansion with even partial quotients
• La théorie de Fredholm
• A Simple Unpredictable Pseudo-Random Number Generator
• Compact Composition Operators on Spaces of Boundary-Regular Holomorphic Functions
• Distribution of Lévy constants for quadratic numbers
• Analysis of the subtractive algorithm for greatest common divisors
• Continued fractions and density results for Dedekind sums.
• A Fast Monte-Carlo Test for Primality
• Über die mittlere Schrittanzahl bei Divisionsalgorithmen
• Dynamical Zeta Functions for Piecewise Monotone Maps of the Interval
• Opérateurs de Ruelle-Mayer généralisés et analyse en moyenne des algorithmes d'Euclide et de Gauss
• An Average-Case Analysis of the Gaussian Algorithm for Lattice Reduction
• On the theorem of Gauss-Kusmin-Lévy and a Frobenius-type theorem for function spaces
• Analytic analysis of algorithms
• Généralisation du théorème de Ikehara
• Produits tensoriels topologiques et espaces nucléaires
• The number of steps in the Euclidean algorithm
• The number of steps in the Euclidean algorithm