Analysis of the continued logarithm algorithm

DOI10.1007/978-3-319-77404-6_61zbMATH Open1506.11155arXiv1801.10139OpenAlexW2963111817MaRDI QIDQ2294741FDOQ2294741

Authors: Pablo Rotondo, Alfredo Viola, Brigitte Vallée 

Publication date: 12 February 2020

Abstract: The Continued Logarithm Algorithm - CL for short- introduced by Gosper in 1978 computes the gcd of two integers; it seems very efficient, as it only performs shifts and subtractions. Shallit has studied its worst-case complexity in 2016 and showed it to be linear. We here perform the average-case analysis of the algorithm: we study its main parameters (number of iterations, total number of shifts) and obtain precise asymptotics for their mean values. Our 'dynamical' analysis involves the dynamical system underlying the algorithm, that produces continued fraction expansions whose quotients are powers of 2. Even though this CL system has already been studied by Chan (around 2005), the presence of powers of 2 in the quotients ingrains into the central parameters a dyadic flavour that cannot be grasped solely by studying the CL system. We thus introduce a dyadic component and deal with a two-component system. With this new mixed system at hand, we then provide a complete average-case analysis of the CL algorithm, with explicit constants.

Full work available at URL: https://arxiv.org/abs/1801.10139

Recommendations

• Length of the continued logarithm algorithm on rational inputs
• Dynamics of the binary Euclidean algorithm: Functional analysis and operators
• The Lyapunov tortoise and the dyadic hare
• Analysis of fast versions of the Euclid algorithm
• Regularity of the Euclid algorithm; application to the analysis of fast GCD algorithms

zbMATH Keywords

continued logarithm algorithm (CL)

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Continued fractions and generalizations (11J70) Metric theory of continued fractions (11K50) Continued fraction calculations (number-theoretic aspects) (11Y65) Relations between ergodic theory and number theory (37A44)

Cited In (4)

• Length of the continued logarithm algorithm on rational inputs
• Algorithms for computing signs of \(2 \times 2\) determinants: dynamics and average-case analysis
• Speculatively Redundant Continued Logarithm Representation
• The Lyapunov tortoise and the dyadic hare

This page was built for publication: Analysis of the continued logarithm algorithm

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