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.

  • 5
    $\begingroup$ The paper by Liardet and Stambul seems to consider only irrational numbers. As Emil Jerabek points out, without this restriction, the answer is no. $\endgroup$ – Arno Aug 26 '15 at 11:33
  • $\begingroup$ @IgorRivin I chose to accept your answer despite possibly not being correct in all cases; at least it seems to work in most cases. $\endgroup$ – 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.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.