python中的整数平方根
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/15390807/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Integer square root in python
提问by wim
Is there an integer square root somewhere in python, or in standard libraries? I want it to be exact (i.e. return an integer), and bark if there's no solution.
python或标准库中的某处是否有整数平方根？我希望它是精确的（即返回一个整数），如果没有解决方案，请吠叫。
At the moment I rolled my own naive one:
此刻我推出了自己的天真：
def isqrt(n):
i = int(math.sqrt(n) + 0.5)
if i**2 == n:
return i
raise ValueError('input was not a perfect square')
But it's ugly and I don't really trust it for large integers. I could iterate through the squares and give up if I've exceeded the value, but I assume it would be kinda slow to do something like that. Also I guess I'd probably be reinventing the wheel, something like this must surely exist in python already...
但它很丑，我真的不相信大整数。我可以遍历正方形并在超过该值时放弃，但我认为这样做会有点慢。另外我想我可能会重新发明轮子，像这样的东西肯定已经存在于python中......
采纳答案by user448810
Newton's method works perfectly well on integers:
牛顿的方法在整数上工作得很好：
def isqrt(n):
x = n
y = (x + 1) // 2
while y < x:
x = y
y = (x + n // x) // 2
return x
This returns the largest integer xfor which x* xdoes not exceed n. If you want to check if the result is exactly the square root, simply perform the multiplication to check if nis a perfect square.
这将返回的最大整数X为其中X* X不超过ñ。如果您想检查结果是否正好是平方根，只需执行乘法以检查n是否为完全平方。
I discuss this algorithm, and three other algorithms for calculating square roots, at my blog.
我在我的博客中讨论了这个算法以及其他三个用于计算平方根的算法。
回答by javex
Try this condition (no additional computation):
试试这个条件（没有额外的计算）：
def isqrt(n):
i = math.sqrt(n)
if i != int(i):
raise ValueError('input was not a perfect square')
return i
If you need it to return an int(not a floatwith a trailing zero) then either assign a 2nd variable or compute int(i)twice.
如果您需要它返回一个int（不是float带有尾随零的 a），则分配第二个变量或计算int(i)两次。
回答by martineau
Seems like you could check like this:
好像你可以这样检查：
if int(math.sqrt(n))**2 == n:
print n, 'is a perfect square'
Update:
更新：
As you pointed out the above fails for large values of n. For those the following looks promising, which is an adaptation of the example C code, by Martin Guy @ UKC, June 1985, for the relatively simple looking binary numeral digit-by-digit calculation method mentioned in the Wikipedia article Methods of computing square roots:
正如您所指出的，对于较大的n. 对于那些看起来很有希望的内容，这是对示例 C 代码的改编，作者是 Martin Guy @ UKC，1985 年 6 月，用于维基百科文章计算平方根的方法中提到的相对简单的二进制数字逐位计算方法：
from math import ceil, log
def isqrt(n):
res = 0
bit = 4**int(ceil(log(n, 4))) if n else 0 # smallest power of 4 >= the argument
while bit:
if n >= res + bit:
n -= res + bit
res = (res >> 1) + bit
else:
res >>= 1
bit >>= 2
return res
if __name__ == '__main__':
from math import sqrt # for comparison purposes
for i in range(17)+[2**53, (10**100+1)**2]:
is_perfect_sq = isqrt(i)**2 == i
print '{:21,d}: math.sqrt={:12,.7G}, isqrt={:10,d} {}'.format(
i, sqrt(i), isqrt(i), '(perfect square)' if is_perfect_sq else '')
Output:
输出：
0: math.sqrt= 0, isqrt= 0 (perfect square)
1: math.sqrt= 1, isqrt= 1 (perfect square)
2: math.sqrt= 1.414214, isqrt= 1
3: math.sqrt= 1.732051, isqrt= 1
4: math.sqrt= 2, isqrt= 2 (perfect square)
5: math.sqrt= 2.236068, isqrt= 2
6: math.sqrt= 2.44949, isqrt= 2
7: math.sqrt= 2.645751, isqrt= 2
8: math.sqrt= 2.828427, isqrt= 2
9: math.sqrt= 3, isqrt= 3 (perfect square)
10: math.sqrt= 3.162278, isqrt= 3
11: math.sqrt= 3.316625, isqrt= 3
12: math.sqrt= 3.464102, isqrt= 3
13: math.sqrt= 3.605551, isqrt= 3
14: math.sqrt= 3.741657, isqrt= 3
15: math.sqrt= 3.872983, isqrt= 3
16: math.sqrt= 4, isqrt= 4 (perfect square)
9,007,199,254,740,992: math.sqrt=9.490627E+07, isqrt=94,906,265
100,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,020,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,001: math.sqrt= 1E+100, isqrt=10,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,001 (perfect square)
回答by NPE
Your function fails for large inputs:
您的函数对于大输入失败：
In [26]: isqrt((10**100+1)**2)
ValueError: input was not a perfect square
There is a recipe on the ActiveState sitewhich should hopefully be more reliable since it uses integer maths only. It is based on an earlier StackOverflow question: Writing your own square root function
ActiveState 站点上有一个配方，希望它更可靠，因为它仅使用整数数学。它基于较早的 StackOverflow 问题：编写自己的平方根函数
回答by DSM
One option would be to use the decimalmodule, and do it in sufficiently-precise floats:
一种选择是使用该decimal模块，并以足够精确的浮点数进行操作：
import decimal
def isqrt(n):
nd = decimal.Decimal(n)
with decimal.localcontext() as ctx:
ctx.prec = n.bit_length()
i = int(nd.sqrt())
if i**2 != n:
raise ValueError('input was not a perfect square')
return i
which I think should work:
我认为应该有效：
>>> isqrt(1)
1
>>> isqrt(7**14) == 7**7
True
>>> isqrt(11**1000) == 11**500
True
>>> isqrt(11**1000+1)
Traceback (most recent call last):
File "<ipython-input-121-e80953fb4d8e>", line 1, in <module>
isqrt(11**1000+1)
File "<ipython-input-100-dd91f704e2bd>", line 10, in isqrt
raise ValueError('input was not a perfect square')
ValueError: input was not a perfect square
回答by Octipi
Floats cannot be precisely represented on computers. You can test for a desired proximity setting epsilon to a small value within the accuracy of python's floats.
浮点数无法在计算机上精确表示。您可以将所需的接近度设置 epsilon 测试为在 python 浮点数精度范围内的一个小值。
def isqrt(n):
epsilon = .00000000001
i = int(n**.5 + 0.5)
if abs(i**2 - n) < epsilon:
return i
raise ValueError('input was not a perfect square')
回答by mathmandan
Sorry for the very late response; I just stumbled onto this page. In case anyone visits this page in the future, the python module gmpy2 is designed to work with very large inputs, and includes among other things an integer square root function.
抱歉回复太晚了；我只是偶然发现了这个页面。如果将来有人访问此页面，python 模块 gmpy2 旨在处理非常大的输入，并且包括整数平方根函数等。
Example:
例子：
>>> import gmpy2
>>> gmpy2.isqrt((10**100+1)**2)
mpz(10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001L)
>>> gmpy2.isqrt((10**100+1)**2 - 1)
mpz(10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000L)
Granted, everything will have the "mpz" tag, but mpz's are compatible with int's:
当然，一切都会有“mpz”标签，但 mpz 与 int 兼容：
>>> gmpy2.mpz(3)*4
mpz(12)
>>> int(gmpy2.mpz(12))
12
See my other answerfor a discussion of this method's performance relative to some other answers to this question.
有关此方法的性能相对于该问题的其他答案的讨论，请参阅我的其他答案。
Download: https://code.google.com/p/gmpy/
回答by nibot
Long-hand square root algorithm
长手平方根算法
It turns out that there is an algorithm for computing square roots that you can compute by hand, something like long-division. Each iteration of the algorithm produces exactly one digit of the resulting square root while consuming two digits of the number whose square root you seek. While the "long hand" version of the algorithm is specified in decimal, it works in any base, with binary being simplest to implement and perhaps the fastest to execute (depending on the underlying bignum representation).
事实证明，有一种计算平方根的算法可以手动计算，例如长除法。算法的每次迭代只产生结果平方根的一位数，同时消耗您寻求平方根数的两位数。虽然该算法的“长手”版本以十进制指定，但它适用于任何基数，二进制最容易实现，也许执行速度最快（取决于底层的 bignum 表示）。
Because this algorithm operates on numbers digit-by-digit, it produces exact results for arbitrarily large perfect squares, and for non-perfect-squares, can produce as many digits of precision (to the right of the decimal place) as desired.
由于此算法对数字逐位进行运算，因此它可以为任意大的完美平方产生精确的结果，而对于非完美平方，则可以根据需要产生任意多的精度位数（小数点右侧）。
There are two nice writeups on the "Dr. Math" site that explain the algorithm:
“Dr. Math”网站上有两篇很好的文章解释了算法：
And here's an implementation in Python:
这是 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)
You could easily modify this function to conduct additional iterations to calculate the fractional part of the square root. I was most interested in computing roots of large perfect squares.
您可以轻松修改此函数以进行额外的迭代来计算平方根的小数部分。我最感兴趣的是计算大型完美平方的根。
I'm not sure how this compares to the "integer Newton's method" algorithm. I suspect that Newton's method is faster, since it can in principle generate multiple bits of the solution in one iteration, while the "long hand" algorithm generates exactly one bit of the solution per iteration.
我不确定这与“整数牛顿法”算法相比如何。我怀疑牛顿的方法更快，因为它原则上可以在一次迭代中生成多位解，而“长手”算法每次迭代只生成一位解。
Source repo: https://gist.github.com/tobin/11233492
回答by mathmandan
Here's a very straightforward implementation:
这是一个非常简单的实现：
def i_sqrt(n):
i = n.bit_length() >> 1 # i = floor( (1 + floor(log_2(n))) / 2 )
m = 1 << i # m = 2^i
#
# Fact: (2^(i + 1))^2 > n, so m has at least as many bits
# as the floor of the square root of n.
#
# Proof: (2^(i+1))^2 = 2^(2i + 2) >= 2^(floor(log_2(n)) + 2)
# >= 2^(ceil(log_2(n) + 1) >= 2^(log_2(n) + 1) > 2^(log_2(n)) = n. QED.
#
while m*m > n:
m >>= 1
i -= 1
for k in xrange(i-1, -1, -1):
x = m | (1 << k)
if x*x <= n:
m = x
return m
This is just a binary search. Initialize the value mto be the largest power of 2 that does not exceed the square root, then check whether each smaller bit can be set while keeping the result no larger than the square root. (Check the bits one at a time, in descending order.)
这只是一个二分查找。将值初始化为m不超过平方根的最大 2 次方，然后检查是否可以设置每个较小的位，同时保持结果不大于平方根。（一次检查一位，按降序排列。）
For reasonably large values of n(say, around 10**6000, or around 20000bits), this seems to be:
对于相当大的值n（例如，around10**6000或 around 20000bits），这似乎是：
- Faster than the Newton's method implementation described by user448810.
- Much, much slower than the
gmpy2built-in method in my other answer. - Comparable to, but somewhat slower than, the Longhand Square Root described by nibot.
- 比user448810 描述的牛顿方法实现更快。
- 比我其他答案中的
gmpy2内置方法慢得多。 - 与 nibot描述的长手平方根相当，但比它慢一些。
All of these approaches succeed on inputs of this size, but on my machine, this function takes around 1.5 seconds, while @Nibot's takes about 0.9 seconds, @user448810's takes around 19 seconds, and the gmpy2 built-in method takes less than a millisecond(!). Example:
所有这些方法都在这种大小的输入上成功，但在我的机器上，这个函数需要大约 1.5 秒，而@Nibot 需要大约 0.9 秒，@user448810 需要大约 19 秒，而 gmpy2 内置方法需要不到一毫秒（！）。例子：
>>> import random
>>> import timeit
>>> import gmpy2
>>> r = random.getrandbits
>>> t = timeit.timeit
>>> t('i_sqrt(r(20000))', 'from __main__ import *', number = 5)/5. # This function
1.5102493192883117
>>> t('exact_sqrt(r(20000))', 'from __main__ import *', number = 5)/5. # Nibot
0.8952787937686366
>>> t('isqrt(r(20000))', 'from __main__ import *', number = 5)/5. # user448810
19.326695976676184
>>> t('gmpy2.isqrt(r(20000))', 'from __main__ import *', number = 5)/5. # gmpy2
0.0003599147067689046
>>> all(i_sqrt(n)==isqrt(n)==exact_sqrt(n)[0]==int(gmpy2.isqrt(n)) for n in (r(1500) for i in xrange(1500)))
True
This function can be generalized easily, though it's not quite as nice because I don't have quite as precise of an initial guess for m:
这个函数可以很容易地推广，虽然它不是很好，因为我没有那么精确的初始猜测m：
def i_root(num, root, report_exactness = True):
i = num.bit_length() / root
m = 1 << i
while m ** root < num:
m <<= 1
i += 1
while m ** root > num:
m >>= 1
i -= 1
for k in xrange(i-1, -1, -1):
x = m | (1 << k)
if x ** root <= num:
m = x
if report_exactness:
return m, m ** root == num
return m
However, note that gmpy2also has an i_rootmethod.
不过，注意gmpy2也有i_root方法。
In fact this method could be adapted and applied to any (nonnegative, increasing) function fto determine an "integer inverse of f". However, to choose an efficient initial value of myou'd still want to know something about f.
事实上，这种方法可以适用于任何（非负的、递增的）函数，f以确定“的整数倒数f”。但是，要选择一个有效的初始值，m您仍然需要了解f.
Edit: Thanks to @Greggo for pointing out that the i_sqrtfunction can be rewritten to avoid using any multiplications.This yields an impressive performance boost!
编辑：感谢@Greggo 指出i_sqrt可以重写该函数以避免使用任何乘法。这产生了令人印象深刻的性能提升！
def improved_i_sqrt(n):
assert n >= 0
if n == 0:
return 0
i = n.bit_length() >> 1 # i = floor( (1 + floor(log_2(n))) / 2 )
m = 1 << i # m = 2^i
#
# Fact: (2^(i + 1))^2 > n, so m has at least as many bits
# as the floor of the square root of n.
#
# Proof: (2^(i+1))^2 = 2^(2i + 2) >= 2^(floor(log_2(n)) + 2)
# >= 2^(ceil(log_2(n) + 1) >= 2^(log_2(n) + 1) > 2^(log_2(n)) = n. QED.
#
while (m << i) > n: # (m<<i) = m*(2^i) = m*m
m >>= 1
i -= 1
d = n - (m << i) # d = n-m^2
for k in xrange(i-1, -1, -1):
j = 1 << k
new_diff = d - (((m<<1) | j) << k) # n-(m+2^k)^2 = n-m^2-2*m*2^k-2^(2k)
if new_diff >= 0:
d = new_diff
m |= j
return m
Note that by construction, the kth bit of m << 1is not set, so bitwise-or may be used to implement the addition of (m<<1) + (1<<k). Ultimately I have (2*m*(2**k) + 2**(2*k))written as (((m<<1) | (1<<k)) << k), so it's three shifts and one bitwise-or (followed by a subtraction to get new_diff). Maybe there is still a more efficient way to get this? Regardless, it's far better than multiplying m*m! Compare with above:
请注意，通过构造，未设置的k第 位m << 1，因此可以使用按位或来实现 的加法(m<<1) + (1<<k)。最终我(2*m*(2**k) + 2**(2*k))写成(((m<<1) | (1<<k)) << k)，所以它是三个移位和一个按位或（然后是减法得到new_diff）。也许还有更有效的方法来获得这个？无论如何，它比乘法好得多m*m！与上面比较：
>>> t('improved_i_sqrt(r(20000))', 'from __main__ import *', number = 5)/5.
0.10908999762373242
>>> all(improved_i_sqrt(n) == i_sqrt(n) for n in xrange(10**6))
True
回答by Knut ?ngstr?m
I have compared the different methods given here with a loop:
我将这里给出的不同方法与循环进行了比较：
for i in range (1000000): # 700 msec
r=int(123456781234567**0.5+0.5)
if r**2==123456781234567:rr=r
else:rr=-1
finding that this one is fastest and need no math-import. Very long might fail, but look at this
发现这是最快的，不需要数学导入。很长时间可能会失败，但看看这个
15241576832799734552675677489**0.5 = 123456781234567.0
