# Continued Fractions from Digit Streams

let $x=\sum_{i=1}^{\infty}\delta_i2^{-i},\ \delta_i\in\{0,1\}$.

Is there an algorithm that converts the sequence $(\delta_0,\ \delta_1,\ ...)$ of the binary digits of $x$ to the sequence $[a_0;a_1,\ ...]$ of its continued fraction representation?

Yes, there is. The algorithm is due to Bill Gosper - he is considering the more general problem of doing linear fractional transformations with continued fractions - adding $2^{-i}$ is a special case. See also Liardet and Stambul, 1998 for a fancier (and probably more readable) explanation.

• The paper by Liardet and Stambul seems to consider only irrational numbers. As Emil Jerabek points out, without this restriction, the answer is no. – Arno Aug 26 '15 at 11:33
• @IgorRivin I chose to accept your answer despite possibly not being correct in all cases; at least it seems to work in most cases. – Manfred Weis Aug 26 '15 at 11:59

No, there is not. Already $a_0$ is impossible to determine just by reading finitely many digits (namely, it is $1$ iff $\delta_i=1$ for all $i$). The same goes for the subsequent terms of the continued fraction, mutatis mutandis.

• What if for every index $i$ there is a $j>i$ such that $δ_j = 0$? – Thom Smith Aug 26 '15 at 17:23
• Well, what about it? – Emil Jeřábek Aug 26 '15 at 17:31
• Never mind, that clearly doesn't fix the problem for rationals. – Thom Smith Aug 26 '15 at 17:50

(This should be considered rather a comment on Emil's answer than an own answer; please feel free to downvote).

after some thinking about Emil's negative result, I found a way to possibly "resurrect" the existence of an algorithm by introducing the means of prediction and correction.

Emil's counterexample, in which $\delta_i=1$ for $i\ge i_0$, can be fixed by

• setting $x_0 := 0,\ \delta_0 := 0$
• $x_{i+1} = x_i+(\delta_{i+1}-\delta_i)\frac{\beta^{-i}}{\beta-1}$, where the $\delta$'s denote the digits and the $\beta$'s the base of the number system.

as the $x_{i+1}-x_i$ is zero in case of equal digits, the calculated coefficients of continued fraction in case of a trailing sequence $(\delta_i=\delta_{i+1}=\ ...)$ will be that of $x$ and not modified after $i$ steps.

The above idea however doesn't resolve the case of rational $x$ in general; here the best approximation property of continued fractions may be of use in predicting the true continued fraction of $x$: experiments suggest, that $a_i=0, i>=i_0$ in case of rational $x$, and that the value of one of the non-zero parameters $a_k\in\{a_1,\ ...,a_{i-1}\}$ keeps growing as more digits are processed, while the first $k-1$ parameters do not change after a sufficient number of digits have been processed.
In that case we can set $a_k:=\infty$, yielding $[0;a_1,\ ...,a_{k-1}]$ as the continued fraction of $x\in\mathbb{Q}$ if enough periods in the digit stream have been encountered. I am however not an expert in continued fractions, so I'm not sure if my ideas are correct.