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。如果要检查结果是否正是平方根，只需执行乘法检查n是否是完美的平方。

我在my blog讨论这个算法，以及另外三个计算平方根的算法。

Answer 2

在标准库中更新：Python 3.8 has a ^{} function！

我在小（0…2²²）和大（2⁵⁰⁰⁰¹）输入上对每个（正确的）函数进行了基准测试。在这两种情况下，明显的赢家都是排名第一的^{} suggested by mathmandan，其次是Python 3.8的^{}，第三是ActiveState recipe linked by NPE。ActiveState配方有一系列的分区，可以用移位来代替，这使它更快一些（但仍然落后于本机函数）：

def isqrt(n):
    if n > 0:
        x = 1 << (n.bit_length() + 1 >> 1)
        while True:
            y = (x + n // x) >> 1
            if y >= x:
                return x
            x = y
    elif n == 0:
        return 0
    else:
        raise ValueError("square root not defined for negative numbers")

基准结果：

• ^{} (mathmandan):0.08微秒小，0.07毫秒大
• int(gmpy2.isqrt())*：0.3微秒小，0.07毫秒大
• Python3.8^{}:0.13微秒小，0.9毫秒大
• ActiveState（如上优化）：0.6微秒小，17.0毫秒大
• ActiveState (NPE):1.0微秒小，17.3毫秒大
• castlebravo long-hand:4微秒小，80毫秒大
• mathmandan improved:2.7微秒小，120毫秒大
• martineau（带this correction）：2.3微秒小，140毫秒大
• nibot:8微秒小，1000毫秒大
• mathmandan:1.8微秒小，2200毫秒大
• castlebravo Newton’s method:1.5微秒小，19000毫秒大
• user448810:1.4微秒小，20000毫秒大

（*由于gmpy2.isqrt返回一个gmpy2.mpz对象，该对象的行为主要与int相似，因此可能需要将其转换回int以供某些使用。）

Answer 3

很抱歉，回复太晚了，我刚刚无意中看到这一页。如果将来有人访问这个页面，python模块gmpy2被设计成可以处理非常大的输入，其中包括一个整数平方根函数。

示例：

>>> import gmpy2
>>> gmpy2.isqrt((10**100+1)**2)
mpz(10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001L)
>>> gmpy2.isqrt((10**100+1)**2 - 1)
mpz(10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000L)

当然，所有东西都有“mpz”标签，但mpz与int兼容：

>>> gmpy2.mpz(3)*4
mpz(12)

>>> int(gmpy2.mpz(12))
12

请参阅my other answer以了解有关此方法相对于此问题的其他一些答案的性能的讨论。

下载：https://code.google.com/p/gmpy/