= Solution
Add the unit fractions one at a time, reducing after each addition:
``
procedure toRat(e; var m,n)
require 0 <= e.i <= N and every stored denominator is positive
m := 0
n := 1
j := 0
while j < e.i do
q := e.x[j]
m := m*q+n
n := n*q
Reduce(m,n)
j := j+1
``
The <loop invariant> is that $m/n$ is the <reduced fraction> equal to the sum of the first $j$ terms, with $m\geq0,n>0$. The update is exactly $m/n+1/q=(mq+n)/(nq)$, and the <greatest common divisor> reduction preserves it. The <loop variant> $e.i-j$ decreases to zero. The empty sum gives \b[$0/1$].
An arbitrary stored Egyptian sum can be at least one, so this uses the broader nonnegative-numerator contract of the implementation in part (a), not an unjustified assumption that every intermediate fraction is proper.
Back to article page
