Работа с большими числами в модуле дроби в Python

РЕДАКТИРОВАТЬ: решено, но так как решение было в комментариях, и я не могу принять свое собственное решение со ссылкой на комментарий до завтра, оно все еще открыто. Еще раз большое спасибо этому великому сообществу и его людям

необязательный контекст: я вычисляю решения для уравнения Пелла

http://mathworld.wolfram.com/PellEquation.html

В нижней части страницы находится таблица со значениями для D -> x, y. Мой код прекрасно работает для КАЖДОГО ЗНАЧЕНИЯ, КРОМЕ D = 61. Я полагаю, что он может иметь какое-то отношение к значениям x и y, являющимся очень большими, и, возможно, модуль дроби не может обработать такие большие числа, и есть переполнение? Я сделал замечание, что если я задаю свое входное / начальное значение в виде дроби или десятичной дроби, это изменит мое решение (но только для D = 61). Почему мой код не работает со значением D = 61? Что мне нужно изменить / использовать, чтобы заставить его работать? Большое спасибо за ваше время и помощь.

код:

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)))
Источник

2 ответа

Решение

Большое спасибо GalAbra и jasonharper за ваши ответы. Узнав с уверенностью, что это проблема разрешения (спасибо GalAbra), я понял, что мне нужно больше десятичных знаков для sqrt(D). Я использовал десятичный модуль из Python:

from decimal import *
getcontext().prec = 1000
D = Fraction(Decimal(D).sqrt())

с этим и изменениями, предложенными jasonharper (еще раз спасибо), это работает сейчас.

Источник

Fraction(1/r1) означает вычислить обратную r1 как неточное число с плавающей точкой, а затем найти рациональное приближение этого неточного числа. Ты хочешь Fraction(1, r1) чтобы напрямую указать числитель и знаменатель вашей дроби, без каких-либо ошибок приближения.

Источник
Другие вопросы по тегам