Continued Fractions for Representing Real Numbers

This is something I learned at EuroPython 2011. I think it came up in a lightning talk by Alex Martelli, but I don’t recall exactly.

Continued fractions are a representation of real numbers that allows for arbitrary-precision arithmetic.

If you’ve worked with floating-point numbers in Python (or most any other programming language, for that matter), you are aware of precision problems like this:

x = 1.0 / 3.0
total = 0.0
for i in range(300):
    total += x
print repr(total)
print total == 100.0

This prints 99.99999999999966, not 100.0. The reason is that the IEEE 754 floating-point representation of 1/3 isn’t exact, and this (initially small) error accumulates 300 times.

There is a different representation for real numbers: continued fractions.

  • Consider the number PI = 3.141592653589793.
  • This can also be written as: 3 + 1 / 7.062513305931052
  • This can be written as: 3 + 1 / (7 + 1 / 15.996594406684103)
  • This can be written as: 3 + 1 / (7 + 1 / (15 + 1 / 1.0034172310150002))
  • This can be written as: 3 + 1 / (7 + 1 / (15 + 1 / (1 + 1 / 292.6345908750162)))
  • This can be written as: 3 + 1 / (7 + 1 / (15 + 1 / (1 + 1 / (292 + 1 / 1.5758184357354204))))

This can be stored efficiently in some form of list: PI = [3, 7, 15, 1, 292, 1, ...]. The “cf” module is a Python implementation of continued fractions by Marcin Ciura that uses lazy evaluation. Here’s the previous example rewritten using continued fractions:

from cf import cf
x = cf(1.0) / cf(3.0)
total = cf(0.0)
for i in range(300):
    total += x
print repr(float(total))    # prints 100.0
print total == 100.0

The mathematical background is explained on Wikipedia and in this presentation by Mark Jason Dominus.

Leave a Reply

  

  

  

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Ads