Good Math

Fibonacci’s Greedy Algorithm

The primary algorithm for computing the Egyptian fraction form is a classic example of what computer-science geeks like me call a greedy algorithm. The greedy algorithm doesn’t always generate the shortest possible Egyptian fraction form, but it is guaranteed to terminate with a finite (if ugly) sequence.

The basic idea of the algorithm is this: given a vulgar fraction x/y, its Egyptian form can be computed like this:

Or in a slightly more useful form, here’s the same algorithm written as a Haskell program that returns a list of unit fractions. (For non-Haskell folks out there, x%y is a Haskell-type constructor ...