The Brun gcd algorithm in high dimensions is almost always subtractive

DOI10.1016/J.JSC.2017.07.004MaRDI QIDQ2409010zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

average-case analysisTauberian theoremtransfer operatormultidimensional continued fractionanalytic combinatoricsdynamical analysisDirichlet generating functionsmultiple gcd algorithm

Mathematics Subject Classification ID

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

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

Cites work

• scientific article; zbMATH DE number 3140585 (Why is no real title available?)
• scientific article; zbMATH DE number 3819870 (Why is no real title available?)
• scientific article; zbMATH DE number 1187021 (Why is no real title available?)
• scientific article; zbMATH DE number 3533576 (Why is no real title available?)
• scientific article; zbMATH DE number 3556191 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 1088932 (Why is no real title available?)
• scientific article; zbMATH DE number 1461539 (Why is no real title available?)
• scientific article; zbMATH DE number 1503600 (Why is no real title available?)
• scientific article; zbMATH DE number 1516956 (Why is no real title available?)
• scientific article; zbMATH DE number 1552278 (Why is no real title available?)
• scientific article; zbMATH DE number 799777 (Why is no real title available?)
• A Jacobi algorithm and metric theory for greatest common divisors
• A Note on Lyapunov Theory for Brun Algorithm
• Analysis of the Brun GCD algorithm
• Analytic combinatorics
• Euclidean algorithms are Gaussian
• Euclidean dynamics
• 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)
• Gaussian laws for the main parameters of the Euclid algorithms
• Generating discrete planes with substitutions
• Generation of digital planes using generalized continued-fractions algorithms
• Mesures de Gauss pour des algorithmes de fractions continues multidimensionnelles
• On almost everywhere strong convergence of multi-dimensional continued fraction algorithms
• On decay of correlations in Anosov flows
• Probabilistic analyses of the plain multiple gcd algorithm
• Sur un Theoreme Spectral et son Application aux Noyaux Lipchitziens
• The quality of the diophantine approximations found by the Jacobi--Perron algorithm and related algorithms
• The recurrence function of a random Sturmian word
• Thed-Dimensional Gauss Transformation: Strong Convergence and Lyapunov Exponents
• Théorie ergodique pour des classes d'opérations non completement continues

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)