1{\bf 15.} (This procedure maintains four integers $(A, B, C, D)$ with the
2invariant meaning that \quotation{our remaining job is to output the continued
3fraction for $(Ay B)(Cy D)$, where $y$ is the input yet to come.}) Initially
4set $j \leftarrow k \leftarrow 0$, $(A, B, C, D) \leftarrow (a, b, c, d)$; then
5input $xj$ and set $(A, B, C, D) \leftarrow (Axj B, A, Cxj D, C)$, $j
6\leftarrow j 1$, one or more times until $C D$ has the same sign as $C$.
7(When $j > 1$ and the input has not terminated, we know that $1 < y < \infty$;
8and when $C D$ has the same sign as $C$ we know therefore that $(Ay B)(Cy
9D)$ lies between $(A B)(C D)$ and $AC$.) Now comes the general step: If no
10integer lies strictly between $(A B)(C D)$ and $AC$, output $Xk \leftarrow
11\lfloor AC \rfloor$, and set $(A, B, C, D) \leftarrow (C, D, A X k C, B Xk
12D)$, $k \leftarrow k 1$; otherwise input $xj$ and set $(A, B,C, D) \leftarrow
13(Axj B, A, Cxj D,C)$, $j \leftarrow j 1$. The general step is repeated ad
14infinitum. However, if at any time the \emph{final} $xj$ is input, the algorithm
15immediately switches gears: It outputs the continued fraction for $(Axj
16B)(Cxj D)$, using Euclids algorithm, and terminates.
17 |