Working with increased precision of irrational numbers in python

Question

I am attempting to do a continued fraction derivation of irrational numbers, e.g. sqrt(13), with Python. I have obtained a pretty good solution which is accurate for the first 10 or so iterations:

Set the original number as current remainder
Append floor of current remainder to list of coefficients
Define new remainder as reciprocal of current remainder minus floor
Go to step 2 unless new remainder is 0

This works very well, except for later iterations, where the float precision is producing erroneous coefficients. Once a single coefficient is off, the remaining will automatically be as well.

My question is therefore if there is a way to treat irrational numbers, e.g. sqrt(13), like placeholders (for later substitution) or in a more precise manner?

My current code is as below:

import math


def continued_fraction(x, upper_limit=30):
    a = []
    # should in fact iterate until repetitive cycle is found 
    for i in range(upper_limit):
        a.append(int(x))
        x = 1.0/(x - a[-1])
    return a


if __name__ == '__main__':
    print continued_fraction(math.sqrt(13))

With the resulting output:

[3, 1, 1, 1, 1, 6, 
    1, 1, 1, 1, 6, 
    1, 1, 1, 1, 6, 
    1, 1, 1, 1, 6, 
    1, 1, 1, 1, 7, 2, 1, 4, 2]

And I know for a fact, that the resulting output should be 3, followed by infinite repetitions of the cycle (1, 1, 1, 1, 6), as per Project Euler Problem 64 (which I'm trying to solve).

@slezica Thanks. That helps quite a bit, but errors still occur beginning at coefficients ~15-30 occasionally. — casparjespersen, Oct 14 '16 at 20:47

score 2 · Accepted Answer · edited May 23 '17 at 12:16

2

I don't know of any such placeholders in Python.

However, you may consider using decimal.Decimal which will increase the precision of your math operations but will never guarantee infinite repetitions of the cycle. Why? Is floating point math broken?

The following modification to your code provides correct results for this run up until upper_limit=45:

import math
from decimal import Decimal


def continued_fraction(x, upper_limit=30):
    a = []
    # should in fact iterate until repetitive cycle is found 
    for i in range(upper_limit):
        a.append(int(x))
        x = Decimal(1.0)/(x - a[-1])
    return a


if __name__ == '__main__':
    print (continued_fraction(Decimal(13).sqrt()))

edited May 23 '17 at 12:16

Community

1
1

answered Oct 14 '16 at 20:51

Moses Koledoye

77,341
8
133
139

Can you elaborate on why you believe it is correct up until upper_limit=45? – casparjespersen Oct 14 '16 at 21:08
I tested the code and it gave in after `45`, do you have something different? – Moses Koledoye Oct 14 '16 at 21:08
Alright. At sqrt(557) it breaks at 31. I was hoping you had some mathematical argument based on actual precision, etc. – casparjespersen Oct 14 '16 at 21:11
Not quite. The results will vary for different inputs – Moses Koledoye Oct 14 '16 at 21:14

score 1 · Answer 2 · answered Oct 14 '16 at 21:13

1

You might cast an eye over https://rosettacode.org/wiki/Continued_fraction#Python. It uses the Fractions and Itertools modules.

answered Oct 14 '16 at 21:13

Bill Bell

21,021
5
43
58

score 1 · Answer 3 · answered Oct 14 '16 at 21:29

1

Apparently Marius Becceanu has released an algorithm for the specific continued fraction of sqrt(n), which is iterative and really nice. This algorithm does not require use of any floating points.

answered Oct 14 '16 at 21:29

casparjespersen

3,460
5
38
63

Working with increased precision of irrational numbers in python

3 Answers3