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?
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communitylet $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.
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.
(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
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.