如果检查一数目是一个完全平方
https://stackoverflow.com/questions/2489435
-
21-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我怎么可能检查，如果一个数字是一个完美的场？
速度是不关心，现在，只要工作。
解决方案
对于依赖任何浮点运算（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的情况下， ，绝对速度; - ）...
其他提示
使用牛顿的方法来迅速解决最近的整数的平方根，然后将其平方，看看它是否是你的号。请参阅 isqrt 。
的Python≥3.8具有 math.isqrt 。如果使用Python的旧版本，寻找“def isqrt(n)”实施这里。
import math
def is_square(i: int) -> bool:
return i == math.isqrt(i) ** 2
由于具有浮点运算（如计算平方根的这些方式）的交易时，你可以从不依赖于精确的比较，一个不易出错的实施方法是
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仍然具有足够精细的分辨率来表示附近的一个用于哪些号码的范围内的值我们寻找。
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并打印“它不是一个完美的正方形。”
<强>它无法用于大非正方形如152415789666209426002111556165263283035677490。
如果你有兴趣，我有一个纯粹的数学的响应的一个类似的问题 数学回答＃,"检测完美的正方形的速度比通过提取的平方根".
我自己的执行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滑通过作为真正的(必要的，或其他旁边的方框是无限的循环)。
下一块代码系统地消除权力的4在一个非常快子算法的使用位移和位逻辑操作。我们最终还是没有找到isSquare我们的原n但一个k这减小了些我们正在与并真正加速了巴比伦的方法，但也使得其他检查速度更快。
第三块代码进行一个简单的布尔的位逻辑检验。最重要的三位数，以二进制的任何完美的平方是001.总是如此。保存为主导的零得到的权力从4，无论如何，已经被占了。如果失败的试验，你马上就知道它不是一个正方形。如果通过，你不可能是肯定的。
此外，如果我们结束了一个1为一个测试值然后测试的数量最初有力的4个，或许包括1本身。
喜欢第三个方框，第四测试的地方价值的十进制使用简单的模的操作者，而倾向于抓住值，穿过前面的测试。还有国防部的7,mod8、mod9日和国防部13测试。
第五块代码的检查，对于一些众所周知的完美方的模式。数字结尾的1或9之前是一个多的四个。和数字结尾的5必须结束在5625,0625,225,或025.我不得包含其他人，但意识到他们是多余的或实际上从未使用。
最后，第六块代码类似于很多什么样的顶部回答者-亚历克斯Martelli-回答。基本上认定的平方根使用古巴比伦算法，但是限制它向整数值，同时忽略浮点。完成这两种速度，并延伸的幅度值进行测试.我用的套代替名单，因为它需要较少时间，我用点转移而不是分裂的两个，我潇洒地选择了一个初始价值，更有效。
顺便说一句，我做了测试亚历克斯Martelli的建议测试数量、以及几个数字的许多订单幅度较大，例如：
x=1000199838770766116385386300483414671297203029840113913153824086810909168246772838680374612768821282446322068401699727842499994541063844393713189701844134801239504543830737724442006577672181059194558045164589783791764790043104263404683317158624270845302200548606715007310112016456397357027095564872551184907513312382763025454118825703090010401842892088063527451562032322039937924274426211671442740679624285180817682659081248396873230975882215128049713559849427311798959652681930663843994067353808298002406164092996533923220683447265882968239141724624870704231013642255563984374257471112743917655991279898690480703935007493906644744151022265929975993911186879561257100479593516979735117799410600147341193819147290056586421994333004992422258618475766549646258761885662783430625 ** 2
for i in range(x, x+2):
print(i, isSquare(i))
印刷的以下结果：
1000399717477066534083185452789672211951514938424998708930175541558932213310056978758103599452364409903384901149641614494249195605016959576235097480592396214296565598519295693079257885246632306201885850365687426564365813280963724310434494316592041592681626416195491751015907716210235352495422858432792668507052756279908951163972960239286719854867504108121432187033786444937064356645218196398775923710931242852937602515835035177768967470757847368349565128635934683294155947532322786360581473152034468071184081729335560769488880138928479829695277968766082973795720937033019047838250608170693879209655321034310764422462828792636246742456408134706264621790736361118589122797268261542115823201538743148116654378511916000714911467547209475246784887830649309238110794938892491396597873160778553131774466638923135932135417900066903068192088883207721545109720968467560224268563643820599665232314256575428214983451466488658896488012211237139254674708538347237589290497713613898546363590044902791724541048198769085430459186735166233549186115282574626012296888817453914112423361525305960060329430234696000121420787598967383958525670258016851764034555105019265380321048686563527396844220047826436035333266263375049097675787975100014823583097518824871586828195368306649956481108708929669583308777347960115138098217676704862934389659753628861667169905594181756523762369645897154232744410732552956489694024357481100742138381514396851789639339362228442689184910464071202445106084939268067445115601375050153663645294106475257440167535462278022649865332161044187890625 True
1000399717477066534083185452789672211951514938424998708930175541558932213310056978758103599452364409903384901149641614494249195605016959576235097480592396214296565598519295693079257885246632306201885850365687426564365813280963724310434494316592041592681626416195491751015907716210235352495422858432792668507052756279908951163972960239286719854867504108121432187033786444937064356645218196398775923710931242852937602515835035177768967470757847368349565128635934683294155947532322786360581473152034468071184081729335560769488880138928479829695277968766082973795720937033019047838250608170693879209655321034310764422462828792636246742456408134706264621790736361118589122797268261542115823201538743148116654378511916000714911467547209475246784887830649309238110794938892491396597873160778553131774466638923135932135417900066903068192088883207721545109720968467560224268563643820599665232314256575428214983451466488658896488012211237139254674708538347237589290497713613898546363590044902791724541048198769085430459186735166233549186115282574626012296888817453914112423361525305960060329430234696000121420787598967383958525670258016851764034555105019265380321048686563527396844220047826436035333266263375049097675787975100014823583097518824871586828195368306649956481108708929669583308777347960115138098217676704862934389659753628861667169905594181756523762369645897154232744410732552956489694024357481100742138381514396851789639339362228442689184910464071202445106084939268067445115601375050153663645294106475257440167535462278022649865332161044187890626 False
它这样做在0.33秒钟。
在我看来，我的算法的工作同作为亚历克斯马特利，与所有利益物，但具有更加高度有效的简单试验的拒绝，节省大量的时间，更不用说减少尺寸的试验数通过权力的4，其改善速度、效率、准确性和大小的数字测试.可能尤其是在非蟒蛇的实现。
大约99%的所有整数被驳回，因为非广场之前，巴比伦的根源提取，甚至实施，并在2/3的时间，这将需要巴比伦拒绝整数。虽然这些试验不要加速的过程中，重要的是，减少在所有测试数到一个奇怪的通过将所有权力的4 真的 加速了巴比伦的试验。
我没有时间对比测试。我测试了所有的整数，从1到10万人继承。使用只是巴比伦的方法本身(与我的特别定制的初始猜)它把我的表面的3的平均165秒(100%精确度)。只是使用该逻辑的测试我的算法(不包括巴比伦)，它采取了127秒，它拒绝了99%的所有整数作为非广场没有错误地拒绝任何完美的正方形。那些整数通过，仅有3%的人完全平方(一个更高的密度)。使用全算法之上，采用的逻辑测试和巴比伦的根源提取，我们有100%的准确度，并测试完成中只有14秒。第一个100万整数的大约需要2分45秒的测试。
编辑：我已经能够带来的时间进一步。我可以现在试验整数0到100万在1分钟40秒。很多时间被浪费检查的数据类型和积极性。消除的第一个两个检查和我切下实验的一分钟。一个人必须假定用户是聪明知道那底片和浮动不完美的正方形。
此可以使用的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
如果您增加值的大小被测试，这最终变得相当缓慢（需要接近秒200000比特的正方形），但较为温和的数字（比如说20000位），它仍然快于人类会注意到单个值（〜33毫秒我的机器上）。但因为速度不是主要考虑的因素，这是Python的标准库做到这一点的好办法。
当然，这将是更快使用 gmpy2 和刚刚测试gmpy2.mpz(x).is_square()，但如果第三方软件包是不是你的东西，上面的作品非常好。
我刚刚发布的轻微变化在上面的一些实施例在另一个线程上（查找完美的正方形），我想我会包括什么我张贴在这里有（使用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)
根据不正确作为一个大的非正方形如152415789666209426002111556165263283035677490。
我的答案是：
def is_square(x):
return x**.5 % 1 == 0
，它基本上是一个平方根，然后通过1模剥离的整数部分，并且如果结果为0返回True否则返回False。在这种情况下，x可以是任何大量的，只是没有大到最大浮子数蟒可以处理：1.7976931348623157e + 308
根据不正确作为一个大的非正方形如152415789666209426002111556165263283035677490。
这是我的方法：
def is_square(n) -> bool:
return int(n**0.5)**2 == int(n)
取数的平方根。转换为整数。就拿广场。如果数量相等，那么它是一个完全平方否则不
根据不正确作为一个大的正方形如152415789666209426002111556165263283035677489。
您可以二进制搜索圆角正方形根。平方的结果，看它是否原始值相匹配。
您可能会更好过与FogleBirds答案 - 虽然提防，如浮点运算是近似的，可以抛出这个办法了。你可以在原则上由一个大的整数，这是一个超过一个完美的正方形，例如，由于丢失的精度得到了假阳性。
- 决定如何长的数量会。
- 采取一个三角洲0.000000000000.......000001
- 看看如果(sqrt(x))^2-x大/平等的/小于三角洲和决定基于三角洲的错误。
这响应不属于你的规定的问题，而是我在你发布的代码，即看到一个隐含的问题“如何检查，如果事情是一个整数？”
您通常会得到这个问题的第一个答案是“不”！而且这是真的，在Python中，类型检查通常是不应该做的事情。
对于那些极少数例外，虽然，而不是寻找数字的字符串表示小数点，将要做的是使用的 isinstance 的功能：
>>> isinstance(5,int)
True
>>> isinstance(5.0,int)
False
当然适用于变量，而不是一个值。如果我想，以确定是否的值的是一个整数，我应该这样做：
>>> x=5.0
>>> round(x) == x
True
但正如其他人已经详细介绍，也有这种事情的大多数非玩具的例子被认为是浮点的问题。
如果要循环在一定范围内，做一些对每一个数字，是不是一个完美的广场，你可以做这样的事情：
def non_squares(upper):
next_square = 0
diff = 1
for i in range(0, upper):
if i == next_square:
next_square += diff
diff += 2
continue
yield i
如果您想为每一个是完全平方数做一些事情，发电机就更简单：
(n * n for n in range(upper))
我觉得这个作品，是非常简单的：
import math
def is_square(num):
sqrt = math.sqrt(num)
return sqrt == int(sqrt)
根据不正确作为一个大的非正方形如152415789666209426002111556165263283035677490。
import math
def is_square(n):
sqrt = math.sqrt(n)
return sqrt == int(sqrt)
<强>它无法用于大非正方形如152415789666209426002111556165263283035677490。
