python - 检查一个数字是否是一个完美的正方形

Question

我如何检查一个数字是否是一个完美的正方形？

速度无关紧要，目前，只要工作即可。

Answer 1

依赖任何浮点计算(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)

提示:它基于平方根的“巴比伦算法”，参见 wikipedia 。它确实适用于您有足够内存进行计算的任何正数；-)。

编辑:让我们看一个例子...

x = 12345678987654321234567 ** 2

for i in range(x, x+2):
   print i, is_square(i)

这会根据需要打印(并且在合理的时间内；-):

152415789666209426002111556165263283035677489 True
152415789666209426002111556165263283035677490 False

在您提出基于浮点中间结果的解决方案之前，请确保它们在这个简单的示例中正常工作 - 这并不难(您只需要一些额外的检查，以防 sqrt计算有点偏离)，只是需要一点小心。

然后尝试使用 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 的情况下, 绝对的速度;-)...