Ale*_*lli 109
依赖于任何浮点计算(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
在你提出基于浮点中间结果的解决方案之前,请确保它们在这个简单的例子中正确工作 - 它并不那么难(你只需要一些额外的检查,以防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,纯粹的速度的情况下) ; - )...
Mik*_*ham 16
因为在处理浮点计算时(例如计算平方根的这些方法),你永远不能依赖于精确的比较,所以实现的错误较少.
import math
def is_square(integer):
root = math.sqrt(integer)
return integer == int(root + 0.5) ** 2
试想一下integer是9.math.sqrt(9)可能是3.0,但它也可能是2.99999或类似的东西3.00001,所以平衡结果是不可靠的.知道int取得最低值,首先增加浮动值0.5意味着如果我们在一个float仍然具有足够精确分辨率的范围内,我们将获得我们正在寻找的值,以表示我们正在寻找的数字附近的数字.
0xP*_*Pwn 11
import math
def is_square(n):
sqrt = math.sqrt(n)
return (sqrt - int(sqrt)) == 0
完美的正方形是一个数字,可以表示为两个相等整数的乘积.math.sqrt(number)回来一个float.int(math.sqrt(number))把结果投到了int.
如果平方根是一个整数,例如3,那么math.sqrt(number) - int(math.sqrt(number))它将是0,if语句将是False.如果平方根是一个像3.2这样的实数,那么它将会True打印出"它不是一个完美的正方形".
如果你有兴趣,我对数学堆栈交换中的类似问题有一个纯数学回答,"检测完美方块比提取平方根更快".
我自己实现的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的isSquare,但是如果可能的话,k <n已经按4的幂缩小.这减少了我们使用的数量的大小,并且真正加快了巴比伦方法,但也使得其他检查更快.
第三个代码块执行简单的布尔位逻辑测试.任意完美正方形的二进制最不重要的三位数字是001.总是.无论如何,除了4的幂之外,还要保留已经计入的前导零.如果测试失败,你会立刻知道它不是正方形.如果它通过,你不能确定.
此外,如果我们最终得到一个1作为测试值,那么测试数最初是4的幂,包括1本身.
与第三个块一样,第四个块使用简单模数运算符测试十进制的单位值,并且倾向于捕获滑过前一个测试的值.还有mod 7,mod 8,mod 9和mod 13测试.
第五块代码检查一些众所周知的完美方形图案.以1或9结尾的数字前面加上四的倍数.以5结尾的数字必须以5625,0625,225或025结尾.我已经包含了其他人,但意识到它们是多余的或从未实际使用过.
最后,第六块代码非常类似于顶级回答者 - 亚历克斯马尔泰利 - 回答的问题.基本上使用古老的巴比伦算法找到平方根,但是在忽略浮点的同时将其限制为整数值.完成速度和扩展可测试值的大小.我使用集合而不是列表,因为它花费的时间少得多,我使用了位移而不是除以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%的所有整数被拒绝为非正方形,并且在2/3时巴比伦人拒绝整数.尽管这些测试并没有显着加快这一过程,但是通过将所有4的幂除以所有测试数来减少到奇数,确实加速了巴比伦测试.
我做了时间比较测试.我连续测试了1到10百万的所有整数.仅使用巴比伦方法(使用我特别定制的初始猜测),我的Surface 3平均需要165秒(准确度为100%).仅使用我的算法中的逻辑测试(不包括巴比伦),它花费了127秒,它拒绝了所有整数的99%作为非正方形而没有错误地拒绝任何完美的正方形.在那些通过的整数中,只有3%是完美的正方形(密度高得多).使用上面使用逻辑测试和巴比伦根提取的完整算法,我们具有100%的准确性,并且仅在14秒内完成测试.前100万个整数大约需要2分45秒才能完成测试.
编辑:我已经能够进一步缩短时间.我现在可以在1分40秒内测试0到1亿的整数.浪费了大量时间来检查数据类型和积极性.消除前两个检查,我将实验减少了一分钟.必须假设用户足够聪明才能知道底片和浮子不是完美的正方形.
小智 9
我的回答是：
def is_square(x):
return x**.5 % 1 == 0
它基本上是一个平方根，然后以 1 为模来去除整数部分，如果结果为 0 则返回，True否则返回False。在这种情况下，x 可以是任何大数，只是没有 python 可以处理的最大浮点数大：1.7976931348623157e+308
对于 152415789666209426002111556165263283035677490 等大的非正方形，这是不正确的。
我是Stack Overflow的新手,并快速浏览以找到解决方案.我刚刚在另一个线程(找到完美的正方形)上发布了上面一些示例的略微变化,并且认为我在这里包含了一些略微的变化(使用nsqrt作为临时变量),以防它感兴趣/使用:
import math
def is_square(n):
if not (isinstance(n, int) and (n >= 0)):
return False
else:
nsqrt = math.sqrt(n)
return nsqrt == math.trunc(nsqrt)
可以使用模块来解决此问题，decimal以获取任意的精确平方根并轻松检查“精确度”：
import math
from decimal import localcontext, Context, Inexact
def is_perfect_square(x):
# If you want to allow negative squares, then set x = abs(x) instead
if x < 0:
return False
# Create localized, default context so flags and traps unset
with localcontext(Context()) as ctx:
# Set a precision sufficient to represent x exactly; `x or 1` avoids
# math domain error for log10 when x is 0
ctx.prec = math.ceil(math.log10(x or 1)) + 1 # Wrap ceil call in int() on Py2
# Compute integer square root; don't even store result, just setting flags
ctx.sqrt(x).to_integral_exact()
# If previous line couldn't represent square root as exact int, sets Inexact flag
return not ctx.flags[Inexact]
对于具有真正巨大价值的示范：
# I just kept mashing the numpad for awhile :-)
>>> base = 100009991439393999999393939398348438492389402490289028439083249803434098349083490340934903498034098390834980349083490384903843908309390282930823940230932490340983098349032098324908324098339779438974879480379380439748093874970843479280329708324970832497804329783429874329873429870234987234978034297804329782349783249873249870234987034298703249780349783497832497823497823497803429780324
>>> sqr = base ** 2
>>> sqr ** 0.5 # Too large to use floating point math
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
OverflowError: int too large to convert to float
>>> is_perfect_power(sqr)
True
>>> is_perfect_power(sqr-1)
False
>>> is_perfect_power(sqr+1)
False
如果增加要测试的值的大小，最终会变得很慢（200,000位平方需要接近一秒钟的时间），但是对于更适中的数字（例如20,000位），它仍然比人类注意到的要快单个值（我的机器上约为33毫秒）。但是，由于速度不是您的主要考虑因素，因此这是使用Python标准库实现此目标的好方法。
当然，使用它并进行gmpy2测试会更快得多gmpy2.mpz(x).is_square()，但是如果您不是第三方软件包，那么上面的方法就很好用了。