Length of the continued logarithm algorithm on rational inputs

zbMATH Open1464.11015arXiv1606.03881MaRDI QIDQ5148754FDOQ5148754

Authors: Jeffrey Shallit 

Publication date: 5 February 2021

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.

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

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

zbMATH Keywords

continued fractionscontinued logarithm algorithm

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (5)

• Recurrence speed of multiples of an irrational number.
• Speculatively Redundant Continued Logarithm Representation
• Generalized continued logarithms and related continued fractions
• Title not available (Why is that?)
• 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)