= Solution
Accumulate the product of the $2\times2$ <matrices> from left to right, which matches forward <linked list> traversal.
``
PROCEDURE cf2rat(f: fraction; VAR n, d: INTEGER);
VAR p: fraction; a, b, c, e, x: INTEGER;
BEGIN
a := 1; b := 0; c := 0; e := 1;
p := f;
WHILE p # NIL DO
x := p.head;
a, b, c, e := a*x+b, a, c*x+e, c;
p := p.tail
END;
n := a; d := c
END cf2rat;
``
The four-value assignment is simultaneous, as permitted by the source. With $M(x)=\left(\begin{smallmatrix}x&1\\1&0\end{smallmatrix}\right)$, the <loop invariant> after reading the prefix $x_0,\ldots,x_{t-1}$ is
$$
\begin{pmatrix}a&b\\c&e\end{pmatrix}=M(x_0)\cdots M(x_{t-1}),
$$
with the empty product initialized to the <identity matrix>. Multiplication on the right by $M(x)$ produces exactly the four assignments above. The <associativity of matrix multiplication> allows this left-to-right accumulation even though the recursive conversion groups operations from the right.
At completion, the first column is the numerator/denominator pair for the whole <continued fraction>: the last factor sends $(1,0)^T$ to $(x_n,1)^T$, and each earlier factor applies the recurrence from part (d). The vector $(1,0)^T$ is an algebraic device, not a finite input ratio requiring division by zero. For a nonempty list the resulting $c$ is positive; for a singleton it is $1$. The product has <determinant> $(-1)^{n+1}$, so its first-column entries are coprime. \b[Return $(a,c)$ in linear node-processing time and $O(1)$ auxiliary space], without changing the list.
Back to article page
