The Brun gcd algorithm in high dimensions is almost always subtractive

DOI10.1016/J.JSC.2017.07.004zbMATH Open1427.11143OpenAlexW2735466101MaRDI QIDQ2409010FDOQ2409010

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

Publication date: 10 October 2017

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

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

Recommendations

Analysis of the Brun GCD algorithm
Analysis of generalized continued fraction algorithms over polynomials
Regularity of the Euclid algorithm; application to the analysis of fast GCD algorithms
Sharp Estimates for the Main Parameters of the Euclid Algorithm
Analysis of fast versions of the Euclid algorithm

average-case analysis Tauberian theorem transfer operator multidimensional continued fraction analytic combinatorics dynamical analysis Dirichlet generating functions multiple gcd algorithm

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Number-theoretic algorithms; complexity (11Y16)

Cites Work

Analytic combinatorics
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
On decay of correlations in Anosov flows
Title not available (Why is that?)
Théorie ergodique pour des classes d'opérations non completement continues
Sur un Theoreme Spectral et son Application aux Noyaux Lipchitziens
Exposants caractéristiques de l'algorithme de Jacobi-Perron et de la transformation associée. (Characteristic exponents of the Jacobi-Perron algorithm and of the associated map)
The quality of the diophantine approximations found by the Jacobi--Perron algorithm and related algorithms
Euclidean algorithms are Gaussian
Gaussian laws for the main parameters of the Euclid algorithms
Euclidean dynamics
Title not available (Why is that?)
Title not available (Why is that?)
Mesures de Gauss pour des algorithmes de fractions continues multidimensionnelles
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Thed-Dimensional Gauss Transformation: Strong Convergence and Lyapunov Exponents
Title not available (Why is that?)
Probabilistic analyses of the plain multiple gcd algorithm
A Jacobi algorithm and metric theory for greatest common divisors
Title not available (Why is that?)
On almost everywhere strong convergence of multi-dimensional continued fraction algorithms
Generating discrete planes with substitutions
Analysis of the Brun GCD algorithm
A Note on Lyapunov Theory for Brun Algorithm
The recurrence function of a random Sturmian word
Generation of digital planes using generalized continued-fractions algorithms

Cited In (5)

Analysis of generalized continued fraction algorithms over polynomials
Rational approximations, multidimensional continued fractions, and lattice reduction
On the second Lyapunov exponent of some multidimensional continued fraction algorithms
Analysis of the Brun GCD algorithm
On analogues of Heilbronn's theorem

This page was built for publication: The Brun gcd algorithm in high dimensions is almost always subtractive

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2409010)