Length of the continued logarithm algorithm on rational inputs
arXiv:1606.03881
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.