Length of the continued logarithm algorithm on rational inputs
classification
🧮 math.NT
cs.DS
keywords
algorithmcontinuedlogarithmrationaladditivearoundborweinbound
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.