Bihomographic functions

Operations such as addition and multiplication on continued fractions can be computed as special cases of bihomographic functions, that is, functions of the form:

The coefficients can be seen as elements of a three-dimensional \(2\times 2\times 2\) matrix.

To evalute a bihomographic function on two continued fraction inputs, we need a three-dimensional version of the “magic table”. Before, the first row represented the numerator and the second row the denominator. Now we’ll go into the page, instead of down the page, and we’ll use \(p/q\) to represent this.

Perhaps we should have done this all along. For example, to compute the convergents of \(\pi\):

When computing homographic functions, we sometimes need the reciprocal. For instance, during the first step of a previous example

we notice the last two convergents have the same integer part, so we subtract and output it (i.e. zero) and invert. To perform the latter, we could erase the last two convergents and write \(5/2, 6/5\) in their place, but instead, to preserve our intermediate steps and also because it’s more convenient and familiar, we simply append the new denominator:

It’s understood that not only do we ignore all but the last two terms, but we also ignore all but the last two numbers in those terms. We have thus freed the vertical dimension.

We may now use the horizontal axis for the input \(x = [a_1;a_2,...]\), and the vertical axis for \(y = [b_1; b_2,...]\). We initialize the table with

We perform the three-dimensional analogue of computing a homographic function. We focus on 2x2 blocks, applying the recurrence relations along the \(x\)-axis or \(y\)-axis or both until all four floor to the same integer. We subtract and output that integer, then reciprocate and repeat the process.

Let’s take Gosper’s example of computing

where \(x = \coth 1 = [1;3, 5, 7, 9,...]\) and \(y = \sqrt{6} = [2;2, 4, 2, 4, ...]\).

We start with:

The top two rows are not even well-defined, so we flee along the \(y\)-axis:

The right column of the 2x2 focus block, \(2/1\) and \(5/2\), have the same integer part, so we move to the right to escape the disagreeable left column:

The 2x2 block has yet to reach a consensus on the integer part, so we keep moving right.

Now all four terms in question floor to \(1\), so we output \(1\), subtract it from each term, and invert:

Recall the only terms that matter now are \(2/0, 7/1, 4/1, 14/6\); all other numbers could be erased if desired. These floor to distinct values, so we move on. Either axis will do; we pick the vertical first because the numbers are smaller. Two steps later:

Now all four floor to give \(2\), which we output and subtract before inverting:

The bottom two agree so we move along the \(y\)-axis.

This yields \(1\). And so on:

We sometimes refer to this procedure as the quadratic algorithm.