python中的整数平方根

Question

在python或标准库中的某个地方是否存在整数平方根？我希望它是准确的（即返回一个整数），如果没有解决办法，可以吠叫。

此刻，我滚动了自己的幼稚：

def isqrt(n):
    i = int(math.sqrt(n) + 0.5)
    if i**2 == n:
        return i
    raise ValueError('input was not a perfect square')

但这很丑陋，我不太相信大整数。我可以遍历正方形，如果超出了该值，则放弃，但是我认为做这样的事情有点慢。另外我想我可能正在重新发明轮子，像这样的东西肯定已经存在于python中了…

Answer 1

牛顿的方法在整数上工作得很好：

def isqrt(n):
    x = n
    y = (x + 1) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x

这将返回的最大整数 X 为其中 X * X 不超过 ñ 。如果要检查结果是否恰好是平方根，只需执行乘法以检查 n 是否为理想平方。

我在博客上讨论了该算法以及其他三种用于计算平方根的算法。