为什么 math.sqrt() 对于大数不正确？

Question

为什么math模块返回错误的结果？

第一次测试

A = 12345678917
print 'A =',A
B = sqrt(A**2)
print 'B =',int(B)

结果

A = 12345678917
B = 12345678917

到这里，结果是正确的。

第二次测试

A = 123456758365483459347856
print 'A =',A
B = sqrt(A**2)
print 'B =',int(B)

结果

A = 123456758365483459347856
B = 123456758365483467538432

这里的结果是不正确的。

为什么会这样？

Answer 1

因为math.sqrt(..)首先将数字转换为浮点数，而浮点数的尾数有限：它只能正确表示数字的一部分。所以float(A**2)不等于A**2。接下来它计算 ，这math.sqrt也大致正确。

大多数使用浮点的函数永远不会完全正确于其对应的整数。浮点计算几乎本质上是近似的。

如果计算A**2得到：

>>> 12345678917**2
152415787921658292889L

现在，如果将其转换为 a float(..)，则会得到：

>>> float(12345678917**2)
1.5241578792165828e+20

但如果你现在问两者是否相等：

>>> float(12345678917**2) == 12345678917**2
False

因此，在将其转换为浮点数时，信息丢失了。

您可以在有关IEEE-754 （浮点工作原理的正式定义）的维基百科文章中详细了解浮点数的工作原理以及为什么它们是近似的。

Answer 2

数学模块的文档指出“它提供了对 C 标准定义的数学函数的访问”。它还指出“除非另有明确说明，所有返回值都是浮点数。”

这些一起意味着平方根函数的参数是浮点值。在大多数系统中，这意味着适合 8 个字节的浮点值，在 C 语言中称为“double”。您的代码在计算平方根之前将整数值转换为这样的值，然后返回这样的值。

然而，8字节浮点值最多可以存储15到17位有效十进制数字。这就是您在结果中得到的结果。

如果您希望平方根具有更高的精度，请使用保证为整数参数提供完整精度的函数。只需进行网络搜索，您就会找到几个。这些通常会采用牛顿-拉夫森方法的变体来迭代并最终得到正确的答案。请注意，这比数学模块的 sqrt 函数要慢得多。

这是我从互联网上修改的例程。我现在无法引用消息来源。此版本也适用于非整数参数，但仅返回平方根的整数部分。

def isqrt(x):
    """Return the integer part of the square root of x, even for very
    large values."""
    if x < 0:
        raise ValueError('square root not defined for negative numbers')
    n = int(x)
    if n == 0:
        return 0
    a, b = divmod(n.bit_length(), 2)
    x = (1 << (a+b)) - 1
    while True:
        y = (x + n//x) // 2
        if y >= x:
            return x
        x = y