EDIT: solved but since the solution was in the comments and I cant accept my own solution reffering to the comment till tomorrow it is still open. Once again a big thank you to this great community and its people
optional context: I am computing sollutions for the Pell equation
http://mathworld.wolfram.com/PellEquation.html
On the buttom of the page is a table with values for D -> x, y. My code works perfectly for EVERY VALUE EXCEPT D = 61. I believe it could have something to do with the values of x and y being very big and maybe the fraction module cant handle such big numbers and there is an overflow? I made the observation, that whether I give my input/ starting value as a fraction or a decimal changes my solution (but only for D = 61). Why is my code failing with the value of D = 61? What do I need to change/use to get it to work? Thank you very much for your time and help.
code:
from math import sqrt, floor
from fractions import Fraction
def continued_fraction(D):
# to make sure it is not a problem on converting decimals to fractions I made EVERYTHING a fraction (which shouldnt and didnt affect the output)
# input is the value for D, output is a tuple with (x, y)
D = Fraction(sqrt(D))
aS = []
a0 = D
r1 = Fraction(D - floor(D))
a = Fraction(a0 - r1)
r = Fraction(-1)
count = 0
while a <= 2*floor(D):
aS.append((a, count))
if a == 2*floor(D):
if count % 2 == 0:
break
else:
r = count
if count == 2*r:
break
try:
a0 = Fraction(1/r1)
except ZeroDivisionError:
break
r1 = Fraction(a0 - floor(a0))
a = Fraction(a0 - r1)
count += 1
pS = []
qS = []
a0 = Fraction(floor(D))
p0 = a0
p1 = Fraction(a0 * aS[1][0] + 1)
q0 = Fraction(1)
q1 = Fraction(aS[1][0])
count = 2
while count < len(aS):
pS.append((p0, count - 2))
qS.append((q0, count - 2))
pn = Fraction(aS[count][0] * p1 + p0)
qn = Fraction(aS[count][0] * q1 + q0)
p0 = Fraction(p1)
p1 = Fraction(pn)
q0 = Fraction(q1)
q1 = Fraction(qn)
count += 1
pS.append((p0, count-1))
#pS.append((p1, count))
qS.append((q0, count - 1))
#qS.append((q1, count))
#print(pS)
#print(qS)
return Fraction(pS[-1][0]), Fraction(qS[-1][0])
print(continued_fraction(Fraction(61)))
A big thanks to GalAbra and jasonharper for your responds. After knowing with certainty, that it is a percision problem (thank you GalAbra) I knew I needed more decimals for the sqrt(D). I used the decimal module from Python:
from decimal import *
getcontext().prec = 1000
D = Fraction(Decimal(D).sqrt())
with this and the change suggested by jasonharper (thank you again) it works now.