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

很抱歉反应太晚；我只是偶然发现了这一页。如果将来有人访问此页面，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

参见我的另一个答案，讨论这个方法相对于这个问题的其他答案的性能。

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

Answer 2

更新：Python3.8有一个math。isqrt标准库中的函数！

我在小（0…2²²）和大（2⁵⁰⁰⁰¹）输入上对每个（正确）函数进行了基准测试。两种情况下的明显赢家都是gmpy2。isqrt首先由mathmandan提出，其次是Python 3.8的数学。第二个是isqrt，第三个是由NPE链接的ActiveState配方。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")

基准结果：

• gmpy2。isqrt（）（mathmandan）：小0.08µs，大0.07 ms
• int（gmpy2.isqrt（））*：小0.3µs，大0.07 ms
• Python3.8math。isqrt：小0.13微秒，大0.9毫秒
• ActiveState（如上所述优化）：小0.6µs，大17.0 ms
• 活性态（NPE）：小1.0µs，大17.3 ms
• castlebravo长柄：小4µs，大80 ms
• mathmandan改进：2.7µs小，120 ms大
• 马提诺（经此校正）：小2.3µs，大140 ms
• 尼波特：小8微秒，大1000毫秒
• mathmandan:1.8µs小，2200 ms大
• castlebravo-Newton法：1.5µs小，19000 ms大
• user448810:1.4微秒小，20000毫秒大

（*由于gmpy2.isqrt返回一个gmpy2.mpz对象，它的行为大部分但不完全像int，您可能需要将其转换回int一些用途。）

Answer 3

牛顿的方法对整数非常有效：

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

这将返回x*x不超过n的最大整数x。如果要检查结果是否正好是平方根，只需执行乘法以检查n是否为完美平方。

我在我的博客上讨论了这个算法，以及其他三个计算平方根的算法。