Length of the continued logarithm algorithm on rational inputs

MaRDI QIDQ5148754zbMATH OpenFDO

Authors Jeffrey Shallit

Publication date 5 February 2021

Full work available at URL https://arxiv.org/abs/1606.03881, http://math.colgate.edu/~integers/u69/u69.pdf

zbMATH Keywords

continued fractionscontinued logarithm algorithm

Mathematics Subject Classification ID

Continued fractions (11A55) Continued fraction calculations (number-theoretic aspects) (11Y65)

Abstract: The continued logarithm algorithm was introduced by Gosper around 1978, and recently studied by Borwein, Calkin, Lindstrom, and Mattingly. In this note I show that the continued logarithm algorithm terminates in at most 2 log_2 p + O(1) steps on input a rational number p/q >= 1. Furthermore, this bound is tight, up to an additive constant.

Recommendations

• Analysis of the continued logarithm algorithm
• scientific article; zbMATH DE number 1919527
• The Computational Complexity of Continued Fractions
• On analogues of Heilbronn's theorem
• Generalized continued logarithms and related continued fractions

Cites work

• Analysis of the continued logarithm algorithm
• Continued logarithms and associated continued fractions
• Generalized continued logarithms and related continued fractions
• Origins of the analysis of the Euclidean algorithm
• Speculatively Redundant Continued Logarithm Representation

Cited in

(5)

• Speculatively Redundant Continued Logarithm Representation
• Generalized continued logarithms and related continued fractions
• Recurrence speed of multiples of an irrational number.
• scientific article; zbMATH DE number 1919527 (Why is no real title available?)
• Analysis of the continued logarithm algorithm

This page was built for publication: Length of the continued logarithm algorithm on rational inputs

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