Fine costs for Euclid's algorithm on polynomials and Farey maps

DOI10.1016/j.aam.2013.11.001zbMath1285.11102OpenAlexW1974936994MaRDI QIDQ2439896

Hitoshi Nakada, Rie Natsui, Brigitte Vallée, Valérie Berthé

Publication date: 25 March 2014

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.aam.2013.11.001

zbMATH Keywords

finite fieldcost functioncontinued fractionscombinatorial analysisbit-complexityLaurent formal power seriesFarey mapbivariate generating functions

Mathematics Subject Classification ID

Asymptotic distribution theory in statistics (62E20) Analysis of algorithms (68W40) Continued fractions and generalizations (11J70) Arithmetic theory of polynomial rings over finite fields (11T55) Metric theory of continued fractions (11K50) Multiplicative structure; Euclidean algorithm; greatest common divisors (11A05)

Related Items (3)

Average-case complexity of the Euclidean algorithm with a fixed polynomial over a finite field ⋮ Farey maps, Diophantine approximation and Bruhat-Tits tree ⋮ Analysis of generalized continued fraction algorithms over polynomials

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Analysis of Euclidean algorithms for polynomials over finite fields
• Algorithms with mediant convergents and their metrical theory
• On convergence rates in the central limit theorems for combinatorial structures
• Dynamical analysis of a class of Euclidean algorithms.
• On continued fraction expansions in positive characteristic: equivalence relations and some metric properties
• Euclidean algorithms are Gaussian
• Presentation functions, fixed points, and a theory of scaling function dynamics.
• Gaussian laws for the main parameters of the Euclid algorithms
• Euclidean dynamics
• The exact length of the Euclidean algorithm in [ X ]
• Precise Analyses of the Right- and Left-Shift Greatest Common Divisor Algorithms for $GF(q)[x$]
• Opérateurs de Ruelle-Mayer généralisés et analyse en moyenne des algorithmes d'Euclide et de Gauss
• The statistics of continued fractions for polynomials over a finite field
• Asymptotic behaviour of the first and second moments for the number of steps in the Euclidean algorithm
• A Simple Estimate for the Number of Steps in the Euclidean Algorithm
• The number of steps in the Euclidean algorithm
• The number of steps in the Euclidean algorithm
• Digits and continuants in Euclidean algorithms. Ergodic versus Tauberian theorems

This page was built for publication: Fine costs for Euclid's algorithm on polynomials and Farey maps