在python中的整数平方根
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中......
牛顿的方法在整数上运作得非常好：
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是否是一个完美的正方形。
我在我的博客上讨论这个算法，以及另外三种计算平方根的算法。
对不起，很迟才回复; 我偶然发现了这个页面。 如果有人在将来访问此页面，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/
长手平方根算法
事实证明，有一种计算平方根的算法，可以通过手工计算，例如长分类。 该算法的每次迭代都会生成所产生的平方根的一个数字，同时会消耗您寻找的平方根的两位数字。 虽然算法的“长手”版本是用十进制指定的，但它可以在任何基础上工作，二进制最简单，也许执行得最快（取决于底层的bignum表示）。
由于此算法对数字逐位进行操作，因此它可以为任意大的完美平方生成精确的结果，对于非完美平方，可以根据需要生成精确度（在小数点右侧）的位数。
在“Dr. Math”网站上有两个很好的文字说明算法：
以下是Python中的一个实现：
def exact_sqrt(x):
"""Calculate the square root of an arbitrarily large integer.
The result of exact_sqrt(x) is a tuple (a, r) such that a**2 + r = x, where
a is the largest integer such that a**2 <= x, and r is the "remainder". If
x is a perfect square, then r will be zero.
The algorithm used is the "long-hand square root" algorithm, as described at
http://mathforum.org/library/drmath/view/52656.html
Tobin Fricke 2014-04-23
Max Planck Institute for Gravitational Physics
Hannover, Germany
"""
N = 0 # Problem so far
a = 0 # Solution so far
# We'll process the number two bits at a time, starting at the MSB
L = x.bit_length()
L += (L % 2) # Round up to the next even number
for i in xrange(L, -1, -1):
# Get the next group of two bits
n = (x >> (2*i)) & 0b11
# Check whether we can reduce the remainder
if ((N - a*a) << 2) + n >= (a<<2) + 1:
b = 1
else:
b = 0
a = (a << 1) | b # Concatenate the next bit of the solution
N = (N << 2) | n # Concatenate the next bit of the problem
return (a, N-a*a)
您可以轻松修改此函数以执行额外的迭代来计算平方根的小数部分。 我最感兴趣的是计算大型完美广场的根源。
我不确定这与“整数牛顿法”算法相比如何。 我怀疑牛顿的方法更快，因为它原则上可以在一次迭代中生成多位解，而“长手”算法每次迭代只生成一位解。
源回购：https://gist.github.com/tobin/11233492
链接地址: http://www.djcxy.com/p/86635.html