The Brun gcd algorithm in high dimensions is almost always subtractive

DOI10.1016/j.jsc.2017.07.004zbMath1427.11143OpenAlexW2735466101MaRDI QIDQ2409010

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

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

Tauberian theoremaverage-case analysistransfer operatoranalytic combinatoricsmultidimensional continued fractiondynamical analysisDirichlet generating functionsmultiple gcd algorithm

Mathematics Subject Classification ID

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

Related Items (2)

On the second Lyapunov exponent of some multidimensional continued fraction algorithms ⋮ Analysis of generalized continued fraction algorithms over polynomials

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
• The quality of the diophantine approximations found by the Jacobi--Perron algorithm and related algorithms
• Probabilistic analyses of the plain multiple gcd algorithm
• On decay of correlations in Anosov flows
• A Jacobi algorithm and metric theory for greatest common divisors
• Euclidean algorithms are Gaussian
• Gaussian laws for the main parameters of the Euclid algorithms
• Euclidean dynamics
• Théorie ergodique pour des classes d'opérations non completement continues
• Generating Discrete Planes with Substitutions
• Analysis of the Brun Gcd Algorithm
• A Note on Lyapunov Theory for Brun Algorithm
• Mesures de Gauss pour des algorithmes de fractions continues multidimensionnelles
• On almost everywhere strong convergence of multi-dimensional continued fraction algorithms
• Thed-Dimensional Gauss Transformation: Strong Convergence and Lyapunov Exponents
• The recurrence function of a random Sturmian word
• Sur un Theoreme Spectral et son Application aux Noyaux Lipchitziens
• Generation of Digital Planes Using Generalized Continued-Fractions Algorithms
• 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)

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