0

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

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

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

2 回答 2

2

Fraction(1/r1)意味着将 的倒数计算r1为不精确的浮点数，然后找到该不精确数的有理逼近。您想Fraction(1, r1)直接指定分数的分子和分母，而不会出现任何近似误差。

于 2018-01-22T21:47:23.193 回答
1

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

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

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

于 2018-01-23T11:44:05.590 回答