检查一个数字是否为完全平方数
26 个回答
如果你感兴趣的话，我在数学交流网站上有个关于类似问题的纯数学回答。
我自己写的isSquare(n)这个函数可能不是最好的，但我挺喜欢的。为了弄明白这个方法，我花了几个月的时间学习数学理论、数字计算和Python编程，还对比了其他人的实现。我觉得这个方法简单又高效，至今还没见过更好的。你觉得怎么样？
def isSquare(n):
## Trivial checks
if type(n) != int: ## integer
return False
if n < 0: ## positivity
return False
if n == 0: ## 0 pass
return True
## Reduction by powers of 4 with bit-logic
while n&3 == 0:
n=n>>2
## Simple bit-logic test. All perfect squares, in binary,
## end in 001, when powers of 4 are factored out.
if n&7 != 1:
return False
if n==1:
return True ## is power of 4, or even power of 2
## Simple modulo equivalency test
c = n%10
if c in {3, 7}:
return False ## Not 1,4,5,6,9 in mod 10
if n % 7 in {3, 5, 6}:
return False ## Not 1,2,4 mod 7
if n % 9 in {2,3,5,6,8}:
return False
if n % 13 in {2,5,6,7,8,11}:
return False
## Other patterns
if c == 5: ## if it ends in a 5
if (n//10)%10 != 2:
return False ## then it must end in 25
if (n//100)%10 not in {0,2,6}:
return False ## and in 025, 225, or 625
if (n//100)%10 == 6:
if (n//1000)%10 not in {0,5}:
return False ## that is, 0625 or 5625
else:
if (n//10)%4 != 0:
return False ## (4k)*10 + (1,9)
## Babylonian Algorithm. Finding the integer square root.
## Root extraction.
s = (len(str(n))-1) // 2
x = (10**s) * 4
A = {x, n}
while x * x != n:
x = (x + (n // x)) >> 1
if x in A:
return False
A.add(x)
return True
这个方法很直接。首先，它检查输入的数字是不是整数，并且是正数。否则就没必要继续了。0被当作True处理（这是必要的，否则接下来的代码会陷入无限循环）。
接下来的代码块使用位移和位逻辑操作，快速地去掉4的幂。我们最终不是在找原始数字n的平方，而是在找一个比n小的k<n，这个k是通过去掉4的幂缩小后的。这可以减少我们处理的数字大小，真的加快了巴比伦方法的速度，同时也让其他检查变得更快。
第三个代码块进行一个简单的布尔位逻辑测试。任何完美平方的最低三位二进制数总是001。除了由于4的幂导致的前导零，这个情况已经考虑过了。如果测试失败，你立刻就知道它不是平方数。如果测试通过，你就不能确定了。
另外，如果测试值最后得到1，那么这个测试数字最初就是4的幂，可能包括1本身。
第四个代码块像第三个一样，使用简单的取模运算来测试十进制的个位数，通常能捕捉到前一个测试漏掉的值。它还进行了模7、模8、模9和模13的测试。
第五个代码块检查一些众所周知的完美平方模式。以1或9结尾的数字前面一定是4的倍数。而以5结尾的数字必须以5625、0625、225或025结尾。我原本还包括了其他的，但后来发现它们是多余的，或者根本没用过。
最后，第六个代码块和顶级回答者Alex Martelli的答案非常相似。基本上是用古老的巴比伦算法找平方根，但限制在整数值上，忽略小数部分。这样做是为了提高速度，并扩展可测试的数值范围。我用集合而不是列表，因为集合的处理速度更快，我用位移代替了除以2，并且更聪明地选择了初始起始值。
顺便说一下，我测试了Alex Martelli推荐的测试数字，还有一些大得多的数字，比如：
x=1000199838770766116385386300483414671297203029840113913153824086810909168246772838680374612768821282446322068401699727842499994541063844393713189701844134801239504543830737724442006577672181059194558045164589783791764790043104263404683317158624270845302200548606715007310112016456397357027095564872551184907513312382763025454118825703090010401842892088063527451562032322039937924274426211671442740679624285180817682659081248396873230975882215128049713559849427311798959652681930663843994067353808298002406164092996533923220683447265882968239141724624870704231013642255563984374257471112743917655991279898690480703935007493906644744151022265929975993911186879561257100479593516979735117799410600147341193819147290056586421994333004992422258618475766549646258761885662783430625 ** 2
for i in range(x, x+2):
print(i, isSquare(i))
打印出了以下结果：
1000399717477066534083185452789672211951514938424998708930175541558932213310056978758103599452364409903384901149641614494249195605016959576235097480592396214296565598519295693079257885246632306201885850365687426564365813280963724310434494316592041592681626416195491751015907716210235352495422858432792668507052756279908951163972960239286719854867504108121432187033786444937064356645218196398775923710931242852937602515835035177768967470757847368349565128635934683294155947532322786360581473152034468071184081729335560769488880138928479829695277968766082973795720937033019047838250608170693879209655321034310764422462828792636246742456408134706264621790736361118589122797268261542115823201538743148116654378511916000714911467547209475246784887830649309238110794938892491396597873160778553131774466638923135932135417900066903068192088883207721545109720968467560224268563643820599665232314256575428214983451466488658896488012211237139254674708538347237589290497713613898546363590044902791724541048198769085430459186735166233549186115282574626012296888817453914112423361525305960060329430234696000121420787598967383958525670258016851764034555105019265380321048686563527396844220047826436035333266263375049097675787975100014823583097518824871586828195368306649956481108708929669583308777347960115138098217676704862934389659753628861667169905594181756523762369645897154232744410732552956489694024357481100742138381514396851789639339362228442689184910464071202445106084939268067445115601375050153663645294106475257440167535462278022649865332161044187890625 True
1000399717477066534083185452789672211951514938424998708930175541558932213310056978758103599452364409903384901149641614494249195605016959576235097480592396214296565598519295693079257885246632306201885850365687426564365813280963724310434494316592041592681626416195491751015907716210235352495422858432792668507052756279908951163972960239286719854867504108121432187033786444937064356645218196398775923710931242852937602515835035177768967470757847368349565128635934683294155947532322786360581473152034468071184081729335560769488880138928479829695277968766082973795720937033019047838250608170693879209655321034310764422462828792636246742456408134706264621790736361118589122797268261542115823201538743148116654378511916000714911467547209475246784887830649309238110794938892491396597873160778553131774466638923135932135417900066903068192088883207721545109720968467560224268563643820599665232314256575428214983451466488658896488012211237139254674708538347237589290497713613898546363590044902791724541048198769085430459186735166233549186115282574626012296888817453914112423361525305960060329430234696000121420787598967383958525670258016851764034555105019265380321048686563527396844220047826436035333266263375049097675787975100014823583097518824871586828195368306649956481108708929669583308777347960115138098217676704862934389659753628861667169905594181756523762369645897154232744410732552956489694024357481100742138381514396851789639339362228442689184910464071202445106084939268067445115601375050153663645294106475257440167535462278022649865332161044187890626 False
而且这个过程只用了0.33秒。
在我看来，我的算法和Alex Martelli的工作原理相同，享有所有的好处，但还增加了高效的简单测试拒绝，这节省了很多时间，更不用说通过去掉4的幂来减少测试数字的大小，这提高了速度、效率、准确性和可测试数字的大小。这在非Python的实现中可能尤其明显。
大约99%的整数在进行巴比伦根提取之前就被拒绝为非平方数，且所需时间是巴比伦方法的三分之二。虽然这些测试并没有显著加快过程，但通过去掉所有4的幂使所有测试数字变成奇数，确实加速了巴比伦测试。
我做了一个时间对比测试。我连续测试了从1到1000万的所有整数。仅使用巴比伦方法（加上我特别调整的初始猜测），我的Surface 3平均花了165秒（准确率100%）。仅使用我算法中的逻辑测试（不包括巴比伦方法），花了127秒，拒绝了99%的整数为非平方数，且没有错误地拒绝任何完美平方。在通过的整数中，只有3%是完美平方（密度高得多）。使用上面完整的算法，结合了逻辑测试和巴比伦根提取，我们实现了100%的准确率，测试完成只需14秒。测试前1亿个整数大约需要2分45秒。
编辑：我已经能够进一步缩短时间。现在我可以在1分40秒内测试从0到1亿的整数。检查数据类型和正数的时间浪费了很多。去掉前两个检查，我就能节省1分钟。必须假设用户足够聪明，知道负数和浮点数不是完美平方。
使用牛顿法可以快速找到最接近的整数平方根，然后把这个平方根平方，看看结果是不是你要的数字。详细信息可以查看isqrt。
Python 3.8及以上版本有一个叫math.isqrt的功能。如果你用的是旧版本的Python，可以在这里找到"def isqrt(n)"的实现。
import math
def is_square(i: int) -> bool:
return i == math.isqrt(i) ** 2
依赖浮点数计算（比如 math.sqrt(x) 或 x**0.5）的问题在于，你不能完全确定结果是准确的（对于足够大的整数 x，结果可能不准确，甚至可能导致溢出）。幸运的是，如果你不着急的话，有很多纯整数的方法可以解决这个问题，比如下面这个……：
def is_square(apositiveint):
x = apositiveint // 2
seen = set([x])
while x * x != apositiveint:
x = (x + (apositiveint // x)) // 2
if x in seen: return False
seen.add(x)
return True
for i in range(110, 130):
print i, is_square(i)
提示：这个方法基于“巴比伦算法”来计算平方根，具体可以查看维基百科。它对任何你有足够内存进行计算的正数都有效;-）。
编辑：我们来看一个例子……
x = 12345678987654321234567 ** 2
for i in range(x, x+2):
print i, is_square(i)
这个例子会按预期输出结果（而且时间也很合理;-）：
152415789666209426002111556165263283035677489 True
152415789666209426002111556165263283035677490 False
请在你提出基于浮点数中间结果的解决方案之前，确保它们在这个简单的例子上能正确工作——这并不难（你只需要多加几个检查，以防计算出的平方根有点偏差），只需要稍微小心一点。
然后试试 x**7，找出聪明的方法来解决你会遇到的问题，
OverflowError: long int too large to convert to float
当然，随着数字越来越大，你需要变得越来越聪明。
如果我真的着急的话，我会使用gmpy——不过，这显然是我个人的偏好;-）。
>>> import gmpy
>>> gmpy.is_square(x**7)
1
>>> gmpy.is_square(x**7 + 1)
0
是的，我知道，这太简单了，感觉像是在作弊（有点像我对Python的感觉;-）——完全没有复杂的东西，只有直接和简单（在gmpy的情况下，还有极快的速度;-）……