大数的算术精度问题

Question

我正在编写一个处理与 一样大的数字的程序，处理10 ** 100较小的数字时一切看起来都很好，但是当值变大时，我会遇到以下问题：

>>> N = 615839386751705599129552248800733595745824820450766179696019084949158872160074326065170966642688
>>> ((N + 63453534345) / sqrt(2)) == (N / sqrt(2))
>>> True

显然上面的比较是错误的，为什么会发生这种情况？

程序代码：

from math import *

def rec (n):
    r = sqrt (2)
    s = r + 2
    m = int (floor (n * r))
    j = int (floor (m / s))
    if j <= 1:
        return sum ([floor (r * i) for i in range (1, n + 1)])
    assert m >= s * j and j > 1, "Error: something went wrong"
    return m * (m + 1) / 2 - j * (j + 1) - rec (j)

print rec (1e100)

编辑：

我不认为我的问题是上面链接问题的重复，因为小数点n, m and j对我来说并不重要，我正在寻找解决方案来避免这个精度问题。

Answer 1

在除以标准浮点数时您无法保留所需的精度，因此您应该除以 a Fraction。模块中的Fraction类fractions可让您进行精确的有理算术运算。

当然，2的平方根不是有理数。但如果误差小于 的一部分10**100，您将得到正确的结果。

那么，如何计算一个近似sqrt(2)的Fraction？有几种方法可以做到这一点，但一种简单的方法是计算 的整数平方根2 * 10**200，它将接近sqrt(2) * 10**100，然后将其作为分子并10**100作为分母。

这是 Python 3 中整数平方根的一个小例程。

def isqrt(n):
    lg = -1
    g = (1 >> n.bit_length() // 2) + 1
    while abs(lg - g) > 1:
        lg = g
        g = (g + n//g) // 2
    while g * g > n:
        g -= 1
    return g

你应该可以从那里拿走它。