Continued Fraction Output

Instead of convergents, suppose we wish to output the result of a homographic function as a continued fraction, so that it may be fed to another continued fraction computation. To achieve this, we perform a division with remainder when two successive convergents floor to the same value before continuing. We follow Gosper’s example: rather than erasing terms we no longer need, we move down the page and write in new terms.

Before demonstrating, we introduce a useful way to view the convergents. We always consider the previous convergent with a given convergent \(p_i/q_i\) and think of it as representing the function.

When \(x\) takes the value \(x_{i+1} = [a_{i+1}; a_{i+2}, ...]\), the function returns the exact answer we seek.

Now we show how to output a continued fraction for our above example. We start as before:

At present we seek \( \frac{2+5 x}{5+6 x} \) for \(x = [2;2,...]\). But the last two convergents both floor to 0, so we append 0 to the output and take reciprocals. We only need two previous convergents to compute the next, so we copy two elements from the top row. We are now seeking \( \frac{5+6 x}{2+5x} \) for \(x = [2;2,...]\).

We could erase all the terms apart from those within the rightmost downmost 2x2 box (in bold), but we keep them to show our working. From here, we apply the recurrence relations:

The last two convergents floor to 1, so we append 1 to the output sequence, take remainders and take the reciprocal before proceeding. Several steps later:

We now see \(\frac{5 + 12 x}{1 +5 x}\) where \(x = [2;2,...]\). But this is exactly the state we were in before we output the first \(2\), hence the continued fraction is periodic and we can simply repeat our previous outputs, starting from the second term.