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是否为理想平方。