チェックの場合、番号はスクエア
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
もしI のの急いで、もちろん、私は gmpy - しかし、その後、私は明確に偏ってる; - 。）
>>> import gmpy
>>> gmpy.is_square(x**7)
1
>>> gmpy.is_square(x**7 + 1)
0
他のヒント
はPythonの≥3.8は math.isqrt を持っています。 「def isqrt(n)」実装ここを探して、Pythonの古いバージョンを使用している場合のます。
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はまだそのために1に近い数字を表現するために細かい十分な解像度を持つ範囲にいる場合、我々は我々が探している値を取得しますfloat第一の手段によって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と印刷されます。
、私は<のhref = "に類似した質問への純粋な数学の応答を持ってyoureの興味を持っている場合https://math.stackexchange.com/questions/131330/detecting-perfect-squares-faster-than-by- 『に平方根を抽出することにより、より速くより完璧な正方形を検出速く平方根を抽出することにより、より完璧な正方形の検出抽出-平方根/ 712818＃712818" タイトル=『』>数学stackexchange、』ます。
isSquare（N）の私の独自の実装は、それのような最高のが、私ではないかもしれません。本当にこの方法でクリックして、他の貢献者などに自分自身を比較し、数学の理論、デジタル演算およびPythonプログラミングに私の研究の数ヶ月を要しました。私はそのシンプルさと効率かかわらずが好き。私は良く見られたhavent。あなたの考えを教えてくださいます。
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
かなりまっすぐ進みます。まず、それは我々が整数、そしてその時、正1を持っていることを確認します。そうでなければ意味がありません。これは、（必要に応じて、または他の次のブロックが無限ループである）真などを通じて0滑りをすることができます。
は、コードの次のブロックは、系統的ビットシフトとビット論理演算を使用して非常に高速なサブアルゴリズム4の電力を除去します。私たちは、最終的には当社独自のnのが、kのisSquareを見つけていない は、コードの3番目のブロックは、単純なブールビットロジックテストを実行します。バイナリで、任意の完全な方形の最下位の3桁は、001常にあります。すでに計上されている、とにかく、4の力から生じる先行ゼロ、のために保存します。それがテストに失敗した場合は、すぐにそれが広場をイマイチ知っています。それが合格した場合、あなたは必ずカントます。 また、試験番号は元々おそらく1自体を含む4の電源、であった。 は第3ブロックと同様に、第四の試験簡単モジュラス演算子を用いて小数におけるもの位の値、および前のテストをすり抜けキャッチ値になる傾向があります。また、8 MOD、7 MOD 9 MOD、及びMOD 13試験 周知完全正方形のパターンのいくつかのコードチェックの第五のブロック。 1又は9で終わる番号が4の倍数によって先行されます。そして、5で終わる番号は5625、0625、225、または025.私は他の人が含まれていますが、彼らは冗長または実際に使用されることはありませんでした実現しています。
ちなみに、私やったテストアレックスマルテッリの推奨テスト番号だけでなく、いくつかの数字何桁の大きさが大きくなる、といったます：
x=1000199838770766116385386300483414671297203029840113913153824086810909168246772838680374612768821282446322068401699727842499994541063844393713189701844134801239504543830737724442006577672181059194558045164589783791764790043104263404683317158624270845302200548606715007310112016456397357027095564872551184907513312382763025454118825703090010401842892088063527451562032322039937924274426211671442740679624285180817682659081248396873230975882215128049713559849427311798959652681930663843994067353808298002406164092996533923220683447265882968239141724624870704231013642255563984374257471112743917655991279898690480703935007493906644744151022265929975993911186879561257100479593516979735117799410600147341193819147290056586421994333004992422258618475766549646258761885662783430625 ** 2
for i in range(x, x+2):
print(i, isSquare(i))
以下の結果を印刷
1000399717477066534083185452789672211951514938424998708930175541558932213310056978758103599452364409903384901149641614494249195605016959576235097480592396214296565598519295693079257885246632306201885850365687426564365813280963724310434494316592041592681626416195491751015907716210235352495422858432792668507052756279908951163972960239286719854867504108121432187033786444937064356645218196398775923710931242852937602515835035177768967470757847368349565128635934683294155947532322786360581473152034468071184081729335560769488880138928479829695277968766082973795720937033019047838250608170693879209655321034310764422462828792636246742456408134706264621790736361118589122797268261542115823201538743148116654378511916000714911467547209475246784887830649309238110794938892491396597873160778553131774466638923135932135417900066903068192088883207721545109720968467560224268563643820599665232314256575428214983451466488658896488012211237139254674708538347237589290497713613898546363590044902791724541048198769085430459186735166233549186115282574626012296888817453914112423361525305960060329430234696000121420787598967383958525670258016851764034555105019265380321048686563527396844220047826436035333266263375049097675787975100014823583097518824871586828195368306649956481108708929669583308777347960115138098217676704862934389659753628861667169905594181756523762369645897154232744410732552956489694024357481100742138381514396851789639339362228442689184910464071202445106084939268067445115601375050153663645294106475257440167535462278022649865332161044187890625 True
1000399717477066534083185452789672211951514938424998708930175541558932213310056978758103599452364409903384901149641614494249195605016959576235097480592396214296565598519295693079257885246632306201885850365687426564365813280963724310434494316592041592681626416195491751015907716210235352495422858432792668507052756279908951163972960239286719854867504108121432187033786444937064356645218196398775923710931242852937602515835035177768967470757847368349565128635934683294155947532322786360581473152034468071184081729335560769488880138928479829695277968766082973795720937033019047838250608170693879209655321034310764422462828792636246742456408134706264621790736361118589122797268261542115823201538743148116654378511916000714911467547209475246784887830649309238110794938892491396597873160778553131774466638923135932135417900066903068192088883207721545109720968467560224268563643820599665232314256575428214983451466488658896488012211237139254674708538347237589290497713613898546363590044902791724541048198769085430459186735166233549186115282574626012296888817453914112423361525305960060329430234696000121420787598967383958525670258016851764034555105019265380321048686563527396844220047826436035333266263375049097675787975100014823583097518824871586828195368306649956481108708929669583308777347960115138098217676704862934389659753628861667169905594181756523762369645897154232744410732552956489694024357481100742138381514396851789639339362228442689184910464071202445106084939268067445115601375050153663645294106475257440167535462278022649865332161044187890626 False
そして、それは0.33秒でこれをやっています。
はすべての整数の約99％が非広場として拒否されています。そして、これらのテストはかなり、4のすべての権限を分割することにより奇数にすべての試験数の減少は、の本当にのは、バビロニアのテストを加速することをプロセスのスピードアップをいけないのにます。
私は、時間の比較テストを行いました。私は連続して1から10万人へのすべての整数をテストしました。 （私の特別仕立ての初期推定で）自身でわずかバビロニアの方法を使用して、それは私の表面3（100％の精度で）165秒の平均を取りました。 （バビロニアを除く）私のアルゴリズムでは、単に論理的なテストを使用して、それが127秒を要し、それが誤って任意の完璧な正方形を拒否することなく、非広場など、すべての整数の99％を拒否しました。渡されたこれらの整数の、わずか3％は完全な正方形（非常に高い密度）となりました。論理テスト、バビロニア根抽出の両方を使用する上記の完全なアルゴリズムを使用して、我々は、わずか14秒で100％の精度、および試験終了を有します。最初の100億の整数試験にほぼ2分45秒かかります。
編集：私は、さらに時間をダウンさせることができました。私は今、1分40秒で100万台に整数0をテストすることができます。多くの時間は、データ型と陽性を確認し無駄になっています。非常に最初の2つのチェックを排除し、私は分単位での実験のダウンをカット。一つは、ユーザがネガや山車が完璧な四角ではないことを知っているスマート十分であると仮定しなければなりません。
これは、任意の精度平方根を取得するために 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
は、これは最終的に（20万ビットの正方形のために近い秒にかかります）かなり遅くなるが、より緩やかな数字（例えば20,000ビット）のために、それはより速く、人間よりもまだです個々の値（私のマシン上の〜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
基本的には、平方根、そしてmoduloによる1冊にしたものを整数部とのとき0を返します True その他返戻 False.この場合に行うことが可能ですので任意の多数などの大きさのfloat数がpythonに対応でき:1.7976931348623157e+308
切では 大きな非スクエアなどの152415789666209426002111556165263283035677490.
この方法：
def is_square(n) -> bool:
return int(n**0.5)**2 == int(n)
取りの平方根。に変換する整数です。の広場があります。場合の数に等しい、それにはぴったりな商品となっている広場。
切では 大きなスクエアなどの152415789666209426002111556165263283035677489.
あなたは、おそらくより良いオフFogleBirdsの答えとしています。あなたは、原則的に失われた高精度に、例えば、1以上の完璧な正方形のより大きな整数から偽陽性を得ることができます。
- かの番号となります。
- 取りデルタ0.000000000000.......000001
- 見た場合の(sqrt(x))^2-xが大きい/equal/以下のデルタおよび決定における意思決定スタイルのデルタエラーとなります。
この応答は、「何かが整数であるかどうかを確認する方法？」、あなたの質問に述べたが、私はあなたが投稿コードで参照の暗黙的な問題、すなわちには関係しない。
あなたは、一般的にその質問に取得します最初の答えは「ない！」ですそして、それは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)
