Probabilistic analyses of the plain multiple gcd algorithm

DOI10.1016/j.jsc.2015.08.007zbMath1346.68308OpenAlexW1709787211MaRDI QIDQ898274

Loïck Lhote, Brigitte Vallée, Valérie Berthé

Publication date: 8 December 2015

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

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

zbMATH Keywords

generating functionsanalysis of algorithmstransfer operatorlimit lawsanalytic combinatoricsPerron formuladynamical analysisLandau theorembeta lawgcd algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial probability (60C05) Number-theoretic algorithms; complexity (11Y16) Convergence of probability measures (60B10)

Related Items

Analysis of Summatory Functions of Regular Sequences: Transducer and Pascal's Rhombus ⋮ The Brun gcd algorithm in high dimensions is almost always subtractive ⋮ Storage efficient algorithm for Hermite normal form using LLL ⋮ Analysis of generalized continued fraction algorithms over polynomials ⋮ Asymptotic analysis of regular sequences ⋮ Gaussian behavior of quadratic irrationals

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the thermodynamic formalism for the Gauss map
• Analysis of Euclidean algorithms for polynomials over finite fields
• Continued fraction algorithms, functional operators, and structure constants
• On continued fraction expansions in positive characteristic: equivalence relations and some metric properties
• Euclidean algorithms are Gaussian
• Gaussian laws for the main parameters of the Euclid algorithms
• Euclidean dynamics
• GCD of random linear combinations
• Fast computation of continued fraction expansions.
• Multiple GCDs. probabilistic analysis of the plain algorithm
• The exact length of the Euclidean algorithm in [ X ]
• The statistics of continued fractions for polynomials over a finite field
• Thermodynamic Formalism
• Algorithmic Number Theory
• On the reduction of a random basis
• The number of steps in the Euclidean algorithm
• The number of steps in the Euclidean algorithm