= Solution
Accumulate denominators while reducing the positive residual:
``
procedure fromRat(m,n; var e)
require 0 <= m < n
e.i := 0
while m > 0 do
q := n div m
if n mod m != 0 then q := q+1
assert e.i < N
e.x[e.i] := q
e.i := e.i+1
m := m*q-n
n := n*q
Reduce(m,n)
``
The quotient-and-remainder calculation implements the ceiling exactly. With original inputs $m_0,n_0$, the <loop invariant> is
$$
\frac{m_0}{n_0}=\sum_{0\leq j<e.i}\frac1{e.x[j]}+\frac mn,\qquad 0\leq m<n.
$$
All stored denominators are positive; `e.i` counts precisely the initialized entries. Part (b) makes $m$ a strictly decreasing nonnegative <loop variant>. At termination the residual is zero, so the stored <Egyptian fraction> has the original value. The promised capacity bound justifies the array assertion. Denominators can grow rapidly, so the integer operations require exact sufficiently large storage.
Back to article page
