Print a prefix while following the linked list, counting how many closing parentheses remain. The final reciprocal can be printed without parentheses.The first loop invariant says that
PROCEDURE printCF(f: fraction);
VAR p: fraction; opened: INTEGER;
BEGIN
p := f; opened := 0;
Out.Int(p.head, 0);
p := p.tail;
WHILE p # NIL DO
IF p.tail = NIL THEN
Out.String("+1/"); Out.Int(p.head, 0)
ELSE
Out.String("+1/("); Out.Int(p.head, 0);
opened := opened + 1
END;
p := p.tail
END;
WHILE opened > 0 DO
Out.String(")"); opened := opened - 1
END
END printCF;p is the next unprinted linked list node, the printed text is the correct expression prefix, and opened counts its unmatched opening parentheses. The final node contributes no opening parenthesis; the second loop invariant says that precisely opened closing parentheses remain. Thus [1,2,3,4,5] produces 1+1/(2+1/(3+1/(4+1/5))). A singleton prints just its head. If the first head is negative, its leading minus remains a valid prefix; subsequent heads are positive.The precondition is a finite nonempty continued fraction list. Every dereference is made only for a nonnull pointer. The procedure uses auxiliary space and time linear in the number of nodes, apart from printing their digits. The source's claimed strict upper bound has an exception under its stated definition:
[x0,1] represents . None of these algorithms relies on that incorrect strict bound.Use the Euclidean algorithm with floor quotient and nonnegative remainder, including for a negative numerator:For , Euclidean division gives with . If , the singleton
PROCEDURE rat2cf(n, d: INTEGER): fraction;
VAR q, r: INTEGER; p: fraction;
BEGIN
q := n DIV d; r := n MOD d;
NEW(p); p.head := q; p.tail := NIL;
IF r # 0 THEN p.tail := rat2cf(d, r) END;
RETURN p
END rat2cf;[q] is exact. Otherwiseso the recursive tail represents . Its numerator is positive and greater than its denominator, so every tail head is a positive integer. The new denominator is strictly smaller than , proving algorithm termination by descent through the positive integers.The returned list represents exactly . For example gives
[-3,1,2]; truncating negative division toward zero would violate the required positivity of the tail. There are Euclidean algorithm steps, with output allocation and recursive stack depth linear in the number of generated nodes.Append each quotient directly to the output linked list, retaining a pointer to its last node. The nodes are required output; auxiliary variables remain simple integers and pointers.At the start of each iteration,
PROCEDURE rat2cf(n, d: INTEGER): fraction;
VAR first, last, p: fraction; q, r: INTEGER;
BEGIN
first := NIL; last := NIL;
REPEAT
q := n DIV d; r := n MOD d;
NEW(p); p.head := q; p.tail := NIL;
IF first = NIL THEN first := p
ELSE last.tail := p
END;
last := p;
n := d; d := r
UNTIL d = 0;
RETURN first
END rat2cf;d is positive, and the output prefix consists exactly of the quotients already obtained by the Euclidean algorithm. last points to its final node, or both first and last are null when the prefix is empty. The current ratio n/d is the unexpanded tail of the original continued fraction. The quotient/remainder step extends that prefix by the same value as the recursive version, then replaces the unexpanded ratio by its reciprocal residual tail. If the remainder is zero, no tail remains and the loop stops before another division.The loop variant is the positive current denominator, which strictly decreases after each nonfinal iteration. The input denominator is positive, so at least one node is allocated, including for zero or an integral ratio. This is the same exact conversion with auxiliary space, excluding the returned list, and no input mutation.
Convert the tail first and apply the reciprocal identity. Two output parameters hold the rational number's numerator and denominator.The singleton case is immediate. If the recursive call returns the tail as , then because every tail head is positive. The full value isStructural induction on the finite nonempty linked list proves correctness, and the denominator is always positive even if the first head is negative. If the tail pair is coprime, then ; the base pair is coprime, so the result is in lowest terms. Return
PROCEDURE cf2rat(f: fraction; VAR n, d: INTEGER);
VAR u, v: INTEGER;
BEGIN
IF f.tail = NIL THEN
n := f.head; d := 1
ELSE
cf2rat(f.tail, u, v);
n := f.head * u + v;
d := u
END
END cf2rat;(head*u+v,u) after converting the tail, using linear node-processing time and linear recursive stack space.Accumulate the product of the matrices from left to right, which matches forward linked list traversal.The four-value assignment is simultaneous, as permitted by the source. With , the loop invariant after reading the prefix iswith the empty product initialized to the identity matrix. Multiplication on the right by 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.
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;At completion, the first column is the numerator/denominator pair for the whole continued fraction: the last factor sends to , and each earlier factor applies the recurrence from part (d). The vector is an algebraic device, not a finite input ratio requiring division by zero. For a nonempty list the resulting is positive; for a singleton it is . The product has determinant , so its first-column entries are coprime. Return in linear node-processing time and auxiliary space, without changing the list.
Articles by others on the same topic
There are currently no matching articles.