Analysis of the Brun GCD algorithm

DOI10.1145/2930889.2930899MaRDI QIDQ2985812zbMATH OpenOpenAlexFDO

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

Publication date 10 May 2017

Published in Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2930889.2930899

zbMATH Keywords

analytic combinatoricsaverage-case analysisBrun continued fractionsDirichlet generating functionsdynamical analysisGCD algorithmsTauberian theoremstransfer operators

Mathematics Subject Classification ID

Continued fractions and generalizations (11J70) Number-theoretic algorithms; complexity (11Y16)

Recommendations

• The Brun gcd algorithm in high dimensions is almost always subtractive
• Regularity of the Euclid algorithm; application to the analysis of fast GCD algorithms
• Analysis and geometry of a GCD-algorithm
• Analysis of fast versions of the Euclid algorithm
• Analysis of generalized continued fraction algorithms over polynomials

Cited in

(3)

• The Brun gcd algorithm in high dimensions is almost always subtractive
• scientific article; zbMATH DE number 2154292 (Why is no real title available?)
• Analysis and geometry of a GCD-algorithm

This page was built for publication: Analysis of the Brun GCD algorithm

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