Sorrells Sorrells - 3 months ago 24
Python Question

Weird output when calculating fractions of a square root

I'm trying to find the continued fractions of any non-square number (until it repeats).

For example: input:

23 = [4; 1,3,1,8]


my code works for many numbers (even though it's very clumsy).
It works for 23 where it outputs:

[4, 1, 3, 1, 8, 1, 3, 1]


(Ignore the extra 1, 3, 1)

But when i input 61 it never stops... here a line of the output:

[7, 1, 4, 3, 1, 2, 2, 1, 3, 4, 1, 14, 1, 4, 3, 1, 2, 2, 1, 4, 5, 1, 6900]


After 14 it doesn't repeat like it should (4, 5 instead of 3, 4 and 6900 are out of place)

I'm a bit of a noob when it comes to coding, so it would help alot if someone could tell my why it doesn't work and how i should fix it

Here's my code:

def find_fractions(n):
d = math.sqrt(n)
x = 0
y = 0
safeint = 0
safe = True
a = ["a", "b", "c", "d"]
while a[1:int(len(a) / 2)] != a[int(len(a) / 2) + 1:]:
a.append(math.floor(d))
d = 1 / (d - math.floor(d))
print(a)
safeint += 1
if safeint > 4 and safe:
del a[0]
del a[0]
del a[0]
del a[0]
safe = False
print(a)

find_fractions(23)


Edit: not 63, meant 61

Answer

What you have is a precision error. These calculations are extremely precise, meaning they require many binary digits to represent. The finite floating point precision that your computer uses is sometimes not enough to do this accurately. Somewhere along the line, the behavior of how this inaccuracy is handled in your machine is breaking your calculations. I used the decimal module to handle this large precision.

import math
from decimal import Decimal
from decimal import getcontext

def find_fractions(n):
    d = Decimal(n).sqrt()
    x = 0
    y = 0
    safeint = 0
    safe = True
    a = ["a", "b", "c", "d"]
    while a[1:int(len(a) / 2)] != a[int(len(a) / 2) + 1:]:
        a.append(math.floor(d))
        d = Decimal(1 / (d - math.floor(d)))
        print(a)
        safeint += 1
        if safeint > 4 and safe:
            del a[0]
            del a[0]
            del a[0]
            del a[0]
            safe = False
    print(a)

This gives me the output [7, 1, 4, 3, 1, 2, 2, 1, 3, 4, 1, 14, 1, 4, 3, 1, 2, 2, 1, 3, 4, 1] for input 61. The default number of places for the Decimal class is 28. If necessary, you can set the Decimal objects to use higher precision like so getcontext().prec = x

Here's a the Wikipedia page to review floating point precision. If you'd like I would be happy to give you some suggestions on making your code cleaner as well.

Comments