*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