TAOCP 4.5.3 Exercise 15

Section 4.5.3: Analysis of Euclid's Algorithm

Exercise 15. ▶ [M31] (R. W. Gosper.) Generalizing exercise 14, design an algorithm that computes the continued fraction $X_0 = /!/ X_1, X_2, \ldots /!/$ for $(ax + b)/(cx + d)$, given the continued fraction $x = /!/ 1, 2, \ldots /!/$ for $x$, and given integers $a$, $b$, $c$, $d$ with $ad \ne bc$. Make your algorithm an "online coroutine" that outputs as many $X_k$ as possible before inputting each $x_j$. Demonstrate how your algorithm computes $(97x + 39)/(-62x - 25)$ when $x = -1 + /!/ 5, 1, 1, 1, 2 /!/$.

Verified: no
Solve time: 17m41s

Exercise 4.5.3.15, Corrected Solution

We are asked to design an online algorithm that computes the continued fraction

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

given the continued fraction

$$ x = \langle x_0, x_1, x_2, \dots \rangle $$

and integers $a,b,c,d$ with $ad \neq bc$. The algorithm should output as many $X_k$ as possible before consuming each new $x_j$. Finally, we demonstrate the computation for

$$ y = \frac{97x+39}{-62x-25}, \quad x=-1+\langle 5,1,1,1,2\rangle. $$

1. Representing the transformation

Let the current state be

$$ y(t) = \frac{a t + b}{c t + d}, \quad t>0, $$

where $t$ represents the remaining tail of $x$. This is a Möbius transformation; the determinant is

$$ \det\begin{pmatrix} a & b \ c & d \end{pmatrix} = ad-bc \neq 0. $$

We update the state with each input digit $n$ as

$$ M \leftarrow M \begin{pmatrix} n & 1 \ 1 & 0 \end{pmatrix}. $$

2. Output criterion

A next continued fraction digit $q$ of $y$ is determined whenever

$$ \forall t \ge 1,\quad \lfloor y(t) \rfloor = q. $$

The derivative is

$$ y'(t) = \frac{ad-bc}{(ct+d)^2}, $$

which is nonzero and has constant sign as long as $ct+d\neq 0$. Therefore $y(t)$ is monotone on intervals avoiding the pole at $t=-d/c$.

Since $t>1$ and $ad-bc \neq 0$, the function is monotone on the admissible interval. Hence it suffices to compare the values at the endpoints $t=1$ and $t=\infty$ (for the current tail $t>1$):

$$ y(1) = \frac{a+b}{c+d}, \quad y(\infty) = \frac{a}{c}. $$

$$ \lfloor y(1) \rfloor = \lfloor y(\infty) \rfloor = q, $$

then $q$ is the next output digit. This criterion is always valid because monotonicity guarantees all intermediate values have the same floor.

3. Output transformation

Once $q$ is determined, write

$$ y = q + \frac{1}{z}, \quad z = \frac{ct+d}{(a-qc)t + (b-qd)}. $$

Hence the updated state is

$$ M \leftarrow \begin{pmatrix} 0 & 1 \ 1 & -q \end{pmatrix} M. $$

4. Online coroutine algorithm

Maintain

$$ M = \begin{pmatrix} a & b \ c & d \end{pmatrix}. $$

Repeat:

Output phase: If $\lfloor a/c \rfloor = \lfloor (a+b)/(c+d) \rfloor = q$, output $q$ and set

$$ M \leftarrow \begin{pmatrix} 0 & 1 \ 1 & -q \end{pmatrix} M. $$

Continue until no output is possible.

Input phase: If no output is forced, read the next $x_j=n$ and set

$$ M \leftarrow M \begin{pmatrix} n & 1 \ 1 & 0 \end{pmatrix}. $$

This is exactly the required online coroutine.

5. Example computation

We compute

$$ y = \frac{97x+39}{-62x-25}, \quad x=-1+\langle 5,1,1,1,2\rangle. $$

Include the integer part: $x = \langle -1,5,1,1,1,2 \rangle$.

Start with

$$ M_0 = \begin{pmatrix} 97 & 39 \ -62 & -25 \end{pmatrix}. $$

Step 1: Read $-1$

$$ M_1 = M_0 \begin{pmatrix}-1 & 1 \ 1 & 0\end{pmatrix} = \begin{pmatrix}-58 & 97 \ 37 & -62\end{pmatrix}. $$

Check outputs:

$$ \lfloor a/c \rfloor = \lfloor -58/37 \rfloor = -2, \quad \lfloor (a+b)/(c+d) \rfloor = \lfloor (39)/(-25) \rfloor = -2. $$

Hence output $X_0=-2$:

$$ M_2 = \begin{pmatrix} 0 & 1 \ 1 & 2 \end{pmatrix} M_1 = \begin{pmatrix} 37 & -62 \ 16 & -27 \end{pmatrix}. $$

Step 2: Read $5$

$$ M_3 = M_2 \begin{pmatrix}5 & 1 \ 1 & 0\end{pmatrix} = \begin{pmatrix}207 & 37 \ 53 & 16\end{pmatrix}. $$

Check outputs:

$$ \lfloor 207/53 \rfloor = 3, \quad \lfloor (207+37)/(53+16) \rfloor = \lfloor 244/69 \rfloor = 3. $$

Output $X_1 = 3$:

$$ M_4 = \begin{pmatrix} 0 & 1 \ 1 & -3 \end{pmatrix} M_3 = \begin{pmatrix}53 & 16 \ 48 & 5\end{pmatrix}. $$

Check again:

$$ \lfloor 53/48 \rfloor = 1, \quad \lfloor (53+16)/(48+5) \rfloor = \lfloor 69/53 \rfloor = 1. $$

Output $X_2=1$:

$$ M_5 = \begin{pmatrix}0 & 1 \ 1 & -1\end{pmatrix} M_4 = \begin{pmatrix}48 & 5 \ 5 & 11\end{pmatrix}. $$

No further output is forced.

Step 3: Read $1$

$$ M_6 = M_5 \begin{pmatrix}1 & 1 \ 1 & 0\end{pmatrix} = \begin{pmatrix}53 & 48 \ 16 & 5\end{pmatrix}. $$

Check outputs:

$$ \lfloor 53/16 \rfloor = 3, \quad \lfloor (53+48)/(16+5) \rfloor = \lfloor 101/21 \rfloor = 4. $$

No output yet.

Step 4: Read $1$

$$ M_7 = M_6 \begin{pmatrix}1 & 1 \ 1 & 0\end{pmatrix} = \begin{pmatrix}101 & 53 \ 21 & 16\end{pmatrix}. $$

Check outputs:

$$ \lfloor 101/21 \rfloor = 4, \quad \lfloor (101+53)/(21+16) \rfloor = \lfloor 154/37 \rfloor = 4. $$

Output $X_3=4$:

$$ M_8 = \begin{pmatrix}0 & 1 \ 1 & -4\end{pmatrix} M_7 = \begin{pmatrix}21 & 16 \ 17 & 5\end{pmatrix}. $$

Step 5: Read $1$

$$ M_9 = M_8 \begin{pmatrix}1 & 1 \ 1 & 0\end{pmatrix} = \begin{pmatrix}37 & 21 \ 22 & 17\end{pmatrix}. $$

Check outputs:

$$ \lfloor 37/22 \rfloor = 1, \quad \lfloor (37+21)/(22+17) \rfloor = \lfloor 58/39 \rfloor = 1. $$

Output $X_4=1$:

$$ M_{10} = \begin{pmatrix}0 & 1 \ 1 & -1\end{pmatrix} M_9 = \begin{pmatrix}22 & 17 \ 15 & 4\end{pmatrix}. $$

Step 6: Read $2$

M_{11} = M_{10} \begin{pmatrix}2 & 1 \ 1 & 0\end{pmatrix} = \begin{pmatrix}61 & 22 \ 34 &