I'm trying to generate a very large number of digits in the decimal representation of a continued fraction, but am running into a scaling problem. The more digits I compute, the larger my coefficients become, and so it effectively takes $O(n^2)$ time to generate $n$ digits, since the arithmetic takes longer and longer as the numbers grow.

I'm using a homographic function

$$z = \frac{ax + b}{cx + d}$$

to compute digits, starting with $a=d=1$ and $b=c=0$. Whenever $\frac{a}{c}$ and $\frac{b}{d}$ have the same integer part $i$, I print the digit $i$ and update $z \rightarrow 10(z - i)$, i.e.

$$a \leftarrow 10(a-ic), \qquad b \leftarrow 10(b-id).$$

Otherwise I read in another term $t$ (i.e. $x \rightarrow t + \frac1x$) and update

$$a \leftarrow at+b, \qquad b \leftarrow a, \qquad c \leftarrow ct+d, \qquad d \leftarrow c.$$

The problem is that the denominator coefficients just keep growing arbitrarily, and never have any common factors, so I don't see any way to reduce them.

Is this just a limitation of continued fractions, or is there some clever sub-quadratic way to compute base-$n$ representations?


Your Answer

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

Browse other questions tagged or ask your own question.