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 systems; Euclidean algorithms; Analysis of algorithms; Functional analysis; Average-case complexity; Transfer operators

Mathematics Subject Classification ID

68W05: Nonnumerical algorithms

Related Items

Digits and continuants in Euclidean algorithms. Ergodic versus Tauberian theorems, Small quotients in Euclidean algorithms, The mean number of steps in the Euclidean algorithm with odd partial quotients, A rigorous version of R. P. Brent's model for the binary Euclidean algorithm, Regularity of the Euclid algorithm; application to the analysis of fast GCD algorithms, Euclidean algorithms are Gaussian, Perron-Frobenius operators and the Klein-Gordon equation, Fine costs for Euclid's algorithm on polynomials and Farey maps, Gaussian laws for the main parameters of the Euclid algorithms, Timed Symbolic Dynamics, The dynamics of Pythagorean Triples

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