数値が完全な正方形であるかどうかを確認するにはどうすればよいですか？
今のところ、速度は問題ではありません。
187983 次
21 に答える
128
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の場合は非常に速い） ;-)..。
于 2010-03-22T01:20:45.020 に答える
54
ニュートン法を使用して、最も近い整数平方根にすばやく焦点を合わせ、それを2乗して、それが自分の数であるかどうかを確認します。isqrtを参照してください。
Python≥3.8には。がありmath.isqrtます。古いバージョンのPythonを使用している場合は、ここでdef isqrt(n)" "実装を探してください。
import math
def is_square(i: int) -> bool:
return i == math.isqrt(i) ** 2
于 2010-03-22T01:26:43.510 に答える
21
浮動小数点計算（平方根を計算するこれらの方法など）を処理するときに正確な比較に依存することは決してできないため、エラーが発生しにくい実装になります。
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.999993.00001int0.5float
于 2010-03-22T01:39:50.187 に答える
18
興味があれば、数学スタックエクスチェンジでの同様の質問に対する純粋数学の回答があります。「平方根を抽出するよりも速く完全な正方形を検出する」。
私自身の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は見つかりませんが、可能であれば4の累乗で縮小されたk<nのisSquareが見つかります。これにより、作業している数値のサイズが小さくなり、バビロニア法が実際に高速化されますが、他のチェックも高速になります。
コードの3番目のブロックは、単純なブールビットロジックテストを実行します。完全な正方形の2進数での最下位の3桁は001です。常に。とにかく、すでに説明されている4の累乗から生じる先行ゼロを除いてください。テストに失敗した場合は、正方形ではないことがすぐにわかります。それが合格した場合、あなたは確信が持てません。
また、テスト値が1になると、テスト番号は元々4の累乗であり、おそらく1自体も含まれます。
3番目のブロックと同様に、4番目のブロックは単純な剰余演算子を使用して小数点以下1桁の値をテストし、前のテストをすり抜ける値をキャッチする傾向があります。また、mod 7、mod 8、mod 9、およびmod13のテスト。
コードの5番目のブロックは、よく知られている完全な正方形のパターンのいくつかをチェックします。1または9で終わる数字の前には、4の倍数があります。また、5で終わる番号は、5625、0625、225、または025で終わる必要があります。他の番号も含めましたが、冗長であるか、実際には使用されていないことに気付きました。
最後に、コードの6番目のブロックは、トップアンサーであるAlexMartelliの回答に非常によく似ています。基本的に、古代のバビロニアアルゴリズムを使用して平方根を見つけますが、浮動小数点を無視して整数値に制限します。速度とテスト可能な値の大きさの拡張の両方のために行われます。時間がはるかに短いため、リストの代わりにセットを使用し、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のすべての累乗を分割することによってすべてのテスト数を奇数に減らすと、バビロニアのテストが実際に加速されます。
時間比較テストを行いました。100万から1000万までのすべての整数を連続してテストしました。バビロニア法だけを（私の特別に調整された最初の推測で）使用すると、Surface 3は平均165秒（100％の精度で）かかりました。私のアルゴリズム（バビロニア語を除く）の論理テストだけを使用すると、127秒かかり、完全な正方形を誤って拒否することなく、すべての整数の99％を非正方形として拒否しました。合格した整数のうち、完全な平方（はるかに高密度）であったのはわずか3％でした。論理テストとバビロニアルート抽出の両方を採用する上記の完全なアルゴリズムを使用すると、100％の精度が得られ、テストはわずか14秒で完了します。最初の1億個の整数は、テストに約2分45秒かかります。
編集：私はさらに時間を短縮することができました。これで、0から1億の整数を1分40秒でテストできます。データ型と陽性をチェックするのに多くの時間が無駄になります。最初の2つのチェックを削除すると、実験が1分短縮されます。ネガとフロートが完全な正方形ではないことをユーザーが十分に理解していると想定する必要があります。
于 2017-08-16T23:38:32.233 に答える
12
import math
def is_square(n):
sqrt = math.sqrt(n)
return (sqrt - int(sqrt)) == 0
完全な正方形は、2つの等しい整数の積として表現できる数です。math.sqrt(number)を返しますfloat。int(math.sqrt(number))結果をにキャストしintます。
たとえば、平方根が3のような整数の場合、math.sqrt(number) - int(math.sqrt(number))0になり、ifステートメントはになりますFalse。平方根が3.2のような実数の場合、True「完全な平方ではありません」と出力されます。
152415789666209426002111556165263283035677490などの大きな非正方形の場合は失敗します。
于 2016-06-01T09:58:33.100 に答える
9
私の答えは：
def is_square(x):
return x**.5 % 1 == 0
基本的に平方根を実行し、次に1を法として整数部分を取り除き、結果が0の場合は、それ以外の場合はをTrue返しFalseます。この場合、xは任意の大きな数値にすることができますが、Pythonが処理できる最大浮動小数点数ほど大きくはありません：1.7976931348623157e + 308
152415789666209426002111556165263283035677490などの大きな非正方形の場合は正しくありません。
于 2017-09-30T04:54:09.490 に答える
7
これは、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ビットの正方形の場合は1秒近くかかります）が、中程度の数値（たとえば、20,000ビット）の場合は、人間が気付くよりも高速です。個々の値（私のマシンでは約33ミリ秒）。しかし、速度はあなたの主な関心事ではなかったので、これはPythonの標準ライブラリでそれを行うための良い方法です。
もちろん、使用gmpy2してテストする方がはるかに高速gmpy2.mpz(x).is_square()ですが、サードパーティのパッケージが適切でない場合は、上記が非常にうまく機能します。
于 2016-06-22T01:38:08.113 に答える
6
上記の例のいくつかのわずかなバリエーションを別のスレッドに投稿し（完全な正方形を見つける）、興味がある場合に備えて、ここに投稿したもののわずかなバリエーションを含めると思いました（一時変数として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などの大きな非正方形の場合は正しくありません。
于 2011-04-21T22:04:49.150 に答える
2
これが私の方法です：
def is_square(n) -> bool:
return int(n**0.5)**2 == int(n)
数の平方根を取ります。整数に変換します。正方形を取ります。数が等しい場合、それは完全な正方形です。そうでない場合はそうではありません。
152415789666209426002111556165263283035677489などの大きな正方形には正しくありません。
于 2017-07-18T10:51:32.073 に答える
2
平方根で割った残りの係数（余り）が0の場合、それは完全な正方形です。
def is_square(num: int) -> bool:
return num % math.sqrt(num) == 0
私はこれを1000までの完全な正方形のリストと照合しました。
于 2020-02-07T21:40:19.887 に答える
1
丸められた平方根を二分探索することができます。結果を2乗して、元の値と一致するかどうかを確認します。
FogleBirdsの回答の方がおそらく良いでしょう。ただし、浮動小数点演算は概算であり、このアプローチを失敗させる可能性があるため、注意してください。原則として、たとえば精度が失われたために、完全な正方形より1つ多い大きな整数から誤検知が発生する可能性があります。
于 2010-03-22T01:06:13.633 に答える
1
@AlexMartelliのソリューションの変形set
いつx in seenですかTrue：
- ほとんどの場合、これは最後に追加されたものです。たとえば、1022は'
xsシーケンス511、256、129、68、41、32、31、31を生成します。 - 場合によっては（つまり、完全な平方の前身の場合）、最後から2番目に追加されます。たとえば、 1023は511、256、129、68、41、32、31、32を生成します。
xしたがって、電流が前の電流以上になるとすぐに停止するだけで十分です。
def is_square(n):
assert n > 1
previous = n
x = n // 2
while x * x != n:
x = (x + (n // x)) // 2
if x >= previous:
return False
previous = x
return True
x = 12345678987654321234567 ** 2
assert not is_square(x-1)
assert is_square(x)
assert not is_square(x+1)
1 <n <10**7でテストされた元のアルゴリズムとの同等性。同じ間隔で、このわずかに単純なバリアントは約1.4倍高速です。
于 2020-03-13T09:30:42.113 に答える
1
nの平方根より上から開始すると、連続する項が減少するシーケンスを形成することを観察することにより、バビロニア法を改善することができます。
def is_square(n):
assert n > 1
a = n
b = (a + n // a) // 2
while b < a:
a = b
b = (a + n // a) // 2
return a * a == n
于 2021-07-26T10:26:57.377 に答える
1
完全な正方形の場合、その平方根は整数になり、小数部分は0になります。小数部分をチェックするためにモジュラス演算子を使用でき、0であるかどうかをチェックできます。一部の数値では失敗するため、安全のために、小数部が0の場合でも、平方根の2乗かどうかもチェックします。
import math
def isSquare(n):
root = math.sqrt(n)
if root % 1 == 0:
if int(root) * int(root) == n:
return True
return False
isSquare(4761)
于 2022-01-01T05:38:54.327 に答える
0
- 番号の長さを決定します。
- デルタを取る0.000000000000.......000001
- （sqrt（x））^ 2-xがデルタよりも大きい/等しい/小さいかどうかを確認し、デルタエラーに基づいて決定します。
于 2010-03-22T03:06:29.677 に答える
0
この応答は、あなたが述べた質問には関係しませんが、あなたが投稿したコードにある暗黙の質問、つまり「何かが整数かどうかを確認する方法」に関係します。
一般的にその質問に答える最初の答えは「しないでください！」です。そして、Pythonでは、タイプチェックは通常正しいことではないのは事実です。
ただし、これらのまれな例外については、数値の文字列表現で小数点を探す代わりに、isinstance関数を使用する必要があります。
>>> isinstance(5,int)
True
>>> isinstance(5.0,int)
False
もちろん、これは値ではなく変数に適用されます。値が整数であるかどうかを判断したい場合は、次のようにします。
>>> x=5.0
>>> round(x) == x
True
しかし、他のすべての人が詳細に説明しているように、この種のもののほとんどのおもちゃ以外の例では、考慮すべき浮動小数点の問題があります。
于 2010-03-23T02:17:13.347 に答える
0
範囲をループして、完全な正方形ではないすべての数値に対して何かを実行したい場合は、次のように実行できます。
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))
于 2017-01-30T20:51:20.067 に答える
0
これは機能し、非常に単純だと思います。
import math
def is_square(num):
sqrt = math.sqrt(num)
return sqrt == int(sqrt)
152415789666209426002111556165263283035677490などの大きな非正方形の場合は正しくありません。
于 2017-08-28T07:44:33.637 に答える
0
a=int(input('enter any number'))
flag=0
for i in range(1,a):
if a==i*i:
print(a,'is perfect square number')
flag=1
break
if flag==1:
pass
else:
print(a,'is not perfect square number')
于 2020-05-07T17:44:03.763 に答える
-3
import math
def is_square(n):
sqrt = math.sqrt(n)
return sqrt == int(sqrt)
152415789666209426002111556165263283035677490などの大きな非正方形の場合は失敗します。
于 2017-03-12T09:58:56.193 に答える
-3
アイデアは、i = 1からfloor（sqrt（n））までループを実行し、それを2乗するとnになるかどうかを確認することです。
bool isPerfectSquare(int n)
{
for (int i = 1; i * i <= n; i++) {
// If (i * i = n)
if ((n % i == 0) && (n / i == i)) {
return true;
}
}
return false;
}
于 2020-05-13T11:16:34.300 に答える