function GCD(m,n): integer
a := m
b := n
while b != 0 do
r := a mod b
a := b
b := r
return a
procedure Reduce(var m,n)
require m >= 0 and n > 0
d := GCD(m,n)
m := m div d
n := n div dThe loop invariant is with . The nonnegative loop variant is : when positive, the new remainder is strictly smaller. Thus the final is the positive greatest common divisor. Dividing both numerator and denominator by it preserves the rational number and makes them coprime. The stated proper fraction case is included, but the same code works for every nonnegative numerator, a fact useful in part (d). In particular, zero reduces to .
For , is equivalent to . The largest allowed unit fraction therefore has the smallest such integer denominator:The residual is . From we obtainThus the nonnegative numerator strictly decreases at each nonfinal step, and reduction to lowest terms can only decrease it further. This loop variant proves termination of the greedy Egyptian fraction expansion. The case already has the empty expansion and requires no division by .
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 , the loop invariant isAll stored denominators are positive;
e.i counts precisely the initialized entries. Part (b) makes 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.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+1The loop invariant is that is the reduced fraction equal to the sum of the first terms, with . The update is exactly , and the greatest common divisor reduction preserves it. The loop variant decreases to zero. The empty sum gives .
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.
procedure OutRat(m,n)
Out.Int(m)
Out.String("/")
Out.Int(n)
procedure OutEgypt(e)
if e.i = 0 then
Out.String("0")
else
for j := 0 to e.i-1 do
if j > 0 then Out.String("+")
Out.String("1/")
Out.Int(e.x[j])Ordinary unpadded decimal output and the greedy Egyptian fraction expansion give
5/7 = 1/2+1/5+1/70 for that input. The final newline is supplied by the caller. Stored duplicate denominators, if present in another valid representation, are printed as separate unit fraction occurrences. Articles by others on the same topic
There are currently no matching articles.