python: continued fractions

When transferring pen-and-paper calculations into computer code, issues related to floating point precision tend to arise. For my preferred rapid prototyping language, python, this is the case as well. Of course, you can work with the decimal module, but this does not help you out in each and every case. For example, let’s consider continued fractions.

Every (added, see comments: quadratic) irrational but not transcendental number can be expressed as a continued fraction which is partially periodical. The euclidean algorithm to calculate the corresponding expansion is simple but requires taking the inverse at every step and is, therefore, prone to numerical errors. In fact, even with arbitrary precision you do not work with exact digital numbers but with an infinite amount of numbers on a interval that map to the same digital representation. You can play around with the following code to see the problem: the last line should print only identical values (for sqrt(13)) but does not. Therefore, you have to test for periodicity with an tolerance limit although you work with (potentially) arbitrary precision numbers.

Leave a comment

Your email address will not be published.

2 thoughts on “python: continued fractions”