5

我想了解为什么会发生某些事情。我需要在 Python 中实现整数平方根 (iqrt(64) = 8 = isqrt(80))。我确信天真的方法：

def isqrt(n):
    return int(math.sqrt(n))

当传递的 n 是一个平方数时，必然会偶尔失败，假设 Python 转换为浮点数，然后对浮点数执行平方根计算。例如，调用 isqrt(13*13) 我希望在转换为浮点数并计算 sqrt 之后，你会得到类似 12.999999843 的东西，在转换为整数之后会给我们 12。

但是我执行了大循环测试值，无论大小，总是得到正确的结果。毕竟，似乎没有必要为整数实现一个特殊的平方根！

不理解让我感到困扰，就像本应有效的事情失败时一样。为什么会这样？

关于python中的整数平方根还有另一个问题：Python中的整数平方根

在那里定义的 isqrt() 中，将 +0.5 添加到 n 中，我想这正是为了解决我提到的我所期待的问题，但在特定情况下找不到。

编辑：忘记指定，我使用的是 Python 2.7

4

1 回答 1

4

long在 C 类型为 64 位整数且 C 类型double实现为 64 位 IEEE 浮点数的机器上使用 python 2.7 会产生

>>> import math
>>> x = (2<<53) + 1
>>> int(math.sqrt(x*x)) == x
False

我作弊选择了一个 64 位 IEEE 浮点数不能准确表示的数字（但 python 的整数类型可以）(2<<53) + 1，. Python 2.7 计算x*x为 Python 2.7long整数。（注意：这与 C 不同long；python 2.7 可以表示2<<600为整数，但 C 不能。）

说到2<<600，

>>> import math
>>> x = 2<<600
>>> int(math.sqrt(x*x)) == x
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
OverflowError: long int too large to convert to float
于 2016-01-21T09:32:26.807 回答