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.
Articles by others on the same topic
There are currently no matching articles.