在 Python 的分数模块中处理大数

Question

编辑：已解决，但由于解决方案在评论中，我不能接受我自己的解决方案，直到明天它仍然开放。再次非常感谢这个伟大的社区及其人民

可选上下文：我正在计算 Pell 方程的解

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

页面底部是 table，其中包含 D -> x、y 的值。我的代码适用于除 D = 61 之外的每个值。我相信这可能与 x 和 y 的值非常大有关，也许分数模块无法处理如此大的数字并且出现溢出？我观察到，无论我将我的输入/起始值作为分数还是小数给出都会改变我的解决方案（但仅适用于 D = 61）。为什么我的代码会因 D = 61 的值而失败？我需要 change/use 什么才能让它工作？非常感谢您的时间和帮助。

代码：

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)))

Answer 1

Fraction(1/r1)表示计算r1的倒数作为一个不精确的浮点数，然后求出该不精确数的有理近似值。您希望 Fraction(1, r1) 直接指定分数的分子和分母，而不会出现任何近似错误。

Answer 2

非常感谢 GalAbra 和 jasonharper 的回复。在确定这是一个精度问题（谢谢 GalAbra）之后，我知道我需要更多的 sqrt(D) 小数。我使用了 Python 中的 decimal 模块：

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

有了这个和 jasonharper 建议的更改（再次感谢您），它现在可以工作了。

在 Python 的分数模块中处理大数

working with large numbers in the fraction module in Python

python

math

fractions

python-3.x

continued-fractions