O'Reilly logo

Good Math by Mark C. Chu-Carroll

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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:

images/_pragprog/svg-0017.png

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required