Überprüfen Sie, ob eine Zahl eine Quadratzahl ist
https://stackoverflow.com/questions/2489435
-
21-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Wie kann ich überprüfen, ob eine Zahl eine Quadratzahl ist?
Die Geschwindigkeit ist nicht von Belang, denn jetzt, nur arbeiten.
Lösung
Das Problem auf jeder Floating-Point-Berechnung mit Berufung (math.sqrt(x) oder x**0.5) ist, dass Sie nicht wirklich sicher sein können, es ist genau (für hinreichend große ganze Zahlen x, wird es nicht sein, und vielleicht sogar Überlauf). Zum Glück (wenn man die nicht in Eile ;-) gibt es viele reine ganze Zahl annähert, wie die folgenden ...:
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)
Hinweis: es auf dem „babylonischen Algorithmus“ für Quadratwurzel basiert, finden Sie unter wikipedia . Es hat Arbeit für jede positive Zahl, für die Sie genug Speicher für die Berechnung müssen vollständig ablaufen; -).
Bearbeiten : mal sehen, ein Beispiel ...
x = 12345678987654321234567 ** 2
for i in range(x, x+2):
print i, is_square(i)
Diese Drucke, wie gewünscht (und in einer angemessenen Höhe der Zeit, auch; -):
152415789666209426002111556165263283035677489 True
152415789666209426002111556165263283035677490 False
Bitte, bevor Sie Lösungen auf Basis von Floating-Point-Zwischenergebnisse schlagen, stellen Sie sicher, dass sie korrekt funktionieren auf diesem einfachen Beispiel - es ist nicht , dass hart (Sie nur ein paar zusätzliche Kontrollen im Fall müssen die sqrt berechnetes ist ein wenig aus), nur ein bisschen Pflege braucht.
Und dann mit x**7 versuchen und kluge Weise zu arbeiten, um das Problem finden Sie bekommen,
OverflowError: long int too large to convert to float
Sie müssen mehr und mehr klug wie die Zahlen bekommen weiter wachsen, natürlich.
Wenn ich liegt bei in Eile, natürlich würde ich verwenden gmpy - aber dann bin ich eindeutig voreingenommen; -).
>>> import gmpy
>>> gmpy.is_square(x**7)
1
>>> gmpy.is_square(x**7 + 1)
0
Ja, ich weiß, das ist nur so einfach fühlt es sich an wie Betrug (ein bisschen so, wie ich zu Python fühle im Allgemeinen ;-) - keine Klugheit überhaupt, einfach perfekt Unmittelbarkeit und Einfachheit (und im Fall von gmpy , schiere Geschwindigkeit; -) ...
Andere Tipps
Mit dem Newton-Verfahren, um schnell Null in auf der nächsten ganzen Zahl Quadratwurzel, quadriert sie dann und sehen, ob es Ihre Zahl ist. Siehe isqrt .
Python ≥ 3,8 hat math.isqrt . Wenn eine ältere Version von Python, suchen Sie nach dem „def isqrt(n)“ Implementierung hier .
import math
def is_square(i: int) -> bool:
return i == math.isqrt(i) ** 2
Da Sie nie auf genaue Vergleiche verlassen können, wenn sie mit Gleitkomma-Berechnungen (wie diese Wege zur Berechnung der Quadratwurzel), ein weniger fehleranfällig Implementierung zu tun wäre
import math
def is_square(integer):
root = math.sqrt(integer)
return integer == int(root + 0.5) ** 2
Stellen Sie sich vor integer 9 ist. math.sqrt(9) könnte 3.0, aber es könnte auch so etwas wie 2.99999 oder 3.00001 sein, so das Ergebnis quadriert sofort ist nicht zuverlässig. dass int zu wissen, nimmt den Bodenwert, den Float-Wertes von 0.5 Erhöhung erste Mittel werden wir den Wert bekommen wir suchen, wenn wir in einem Bereich sind, wo float noch fein genug Auflösung hat Zahlen in der Nähe von dem repräsentieren, für die wir suchen.
import math
def is_square(n):
sqrt = math.sqrt(n)
return (sqrt - int(sqrt)) == 0
Ein perfektes Quadrat ist eine Zahl, die als Produkt aus zwei gleichen ganzen Zahlen ausgedrückt werden können. math.sqrt(number) zurückgeben float. int(math.sqrt(number)) wirft das Ergebnis zu int.
Wenn die Quadratwurzel eine ganze Zahl ist, wie 3, zum Beispiel, dann wird math.sqrt(number) - int(math.sqrt(number)) 0, und die if Aussage False sein wird. Wenn die Quadratwurzel eine reelle Zahl wie 3,2 ist, dann wird es True sein und drucken „es ist kein perfektes Quadrat“.
Es ist immer für einen großen nicht-Platz wie 152415789666209426002111556165263283035677490.
Wenn youre interessiert, ich habe eine reine mathematische Antwort auf eine ähnliche Frage unter Mathematik Stack "Extrahieren Erkennung perfekte Quadrate schneller als durch Quadratwurzel" extrahiert.
Meine eigene Implementierung von isSquare (n) kann nicht die beste sein, aber ich mag es. Habe mir mehrere Monate Studium in Mathematik Theorie, digitale Berechnung und Python-Programmierung, mich zu anderen Mitwirkenden zu vergleichen, etc., um wirklich mit dieser Methode klicken. Ich mag seine Einfachheit und Effizienz though. Ich habe nicht besser gesehen. Sagen Sie mir, was Sie denken.
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
ziemlich geradlinig. Zuerst überprüft es, dass wir eine ganze Zahl haben, und eine positive noch dazu. Ansonsten gibt es keinen Punkt. Es läßt 0 durchrutschen wie True (notwendig oder auch nächster Block ist Endlosschleife).
Der nächste Block von Code entfernt systematisch Potenzen von 4 in einem sehr schnellen Unter Algorithmus Bitverschiebung und Bitverknüpfungen. Wir sind schließlich nicht die isSquare unserer ursprünglichen n zu finden, sondern von einem k Der dritte Codeblock führt eine einfache Boolesche Bit-Logik-Test. Die am wenigsten signifikanten drei Ziffern, binär jeder perfekt quadratisch 001. Immer. Speicher für führende Nullen aus Potenzen von 4, wie auch immer, die bereits berücksichtigt wurde. Wenn es den Test nicht besteht, wissen Sie sofort, es ist nicht ein Quadrat. Wenn es passiert, man kann sicher sein. Auch wenn wir mit einem 1 für einen Testwert am Ende dann war der Prüfnummer ursprünglich eine Leistung von 4, einschließlich vielleicht 1 selbst. Wie der dritten Block, die vierten Tests der Einsen-place-Wert in Dezimalform einfachen Modulo-Operator verwendet wird, und neigen dazu, Fang-Werte, die durch den vorhergehenden Test gleiten. Auch ein mod 7, mod 8, mod 9 und 13 mod Test. Der fünfte Block von Code prüft, ob einige der bekannten Quadratmuster. Die Zahlen in 1 oder 9 enden, werden um ein Vielfaches von vier vorgeschaltet. Und Zahlen in 5 enden muss in 5625 enden, 0625, 225, oder 025. I enthalten andere hatten aber klar, sie waren überflüssig oder nie tatsächlich verwendet wird. Schließlich gleicht die sechste Codeblock sehr viel, was die Top-Beantworter - Alex Martelli - Antwort. Grundsätzlich findet die Quadratwurzel des altbabylonische Algorithmus verwendet, aber es auf ganzzahlige Werte zu beschränken, während Gleitkomma ignorierend. Geschieht sowohl für die Geschwindigkeit und die Größen der Werte erstreckt, die prüfbar sind. Ich benutzen Sets statt Listen, weil es viel weniger Zeit in Anspruch nimmt, habe ich Bit-Verschiebungen statt Division durch zwei, und ich intelligent einen anfänglichen Startwert wesentlich effizienter gewählt habe. Übrigens, ich habe Test Alex Martelli empfohlenen Testnummer, sowie ein paar Zahlen viele Aufträge Größenordnung größer, wie zum Beispiel: gedruckt folgende Ergebnisse: Und es tut dies in 0,33 Sekunden. Meiner Meinung nach ist mein Algorithmus funktioniert genauso wie Alex Martelli, mit allen Vorteilen davon, hat aber den zusätzlichen Vorteil, hocheffiziente einfach Test Ablehnungen, die eine Menge Zeit sparen, nicht auf die Verringerung der Größe der Testzahlen zu erwähnen, durch Potenzen von 4, die Geschwindigkeit, Effizienz, Genauigkeit und die Größe der Zahlen verbessert, die prüfbar sind. Wahrscheinlich vor allem in nicht-Python-Implementierungen. Etwa 99% aller ganzen Zahlen als nicht-Platz vor dem babylonischen Radizierend abgelehnt werden, wird auch umgesetzt und in 2/3 der Zeit würde es die babylonische nehmen Sie die ganze Zahl abzulehnen. Und obwohl diese Tests nicht beschleunigt den Prozess, der wesentlich die Reduktion in allen Testzahlen auf eine ungerade durch alle Kräfte Dividieren von 4 wirklich beschleunigt den babylonischen Test. Ich habe eine Zeitvergleichstest. Getestet habe ich alle Zahlen von 1 bis 10 Millionen in Folge. Mit nur die babylonischen Methode selbst (mit meiner speziell ersten Schätzung angepasst) dauerte es meine Oberfläche 3 einen Durchschnitt von 165 Sekunden (mit 100% Genauigkeit). Mit nur die logischen Tests in meinem Algorithmus (mit Ausnahme der babylonischen), ist es 127 Sekunden dauerte, wies sie 99% aller ganzen Zahlen als nicht-Platz ohne fälschlicherweise keine perfekten Quadrate Ablehnung. Von diesen ganzen Zahlen, die vergangen, nur 3% war perfekt Squares (eine viel höhere Dichte). Unter Verwendung den vollständigen Algorithmus oben, die sowohl die logischen Tests und die babylonische Wurzelextraktion verwendet, haben wir 100% Genauigkeit und Test Abschluss in nur 14 Sekunden. Die ersten 100 Millionen ganze Zahlen dauern ca. 2 Minuten und 45 Sekunden, um zu testen. EDIT: Ich konnte die Zeit weiter senken. Ich kann jetzt den ganzen Zahlen 0 bis 100 Millionen in 1 Minute 40 Sekunden testen. Viel Zeit wird verschwendet den Datentyp und die Positivität zu überprüfen. Beseitigen Sie die ersten zwei Kontrollen und schneide ich das Experiment nach unten von einer Minute. Man muss annehmen, der Benutzer intelligent genug, um zu wissen, dass Negative und Schwimmer sind nicht perfekt Quadrate. x=1000199838770766116385386300483414671297203029840113913153824086810909168246772838680374612768821282446322068401699727842499994541063844393713189701844134801239504543830737724442006577672181059194558045164589783791764790043104263404683317158624270845302200548606715007310112016456397357027095564872551184907513312382763025454118825703090010401842892088063527451562032322039937924274426211671442740679624285180817682659081248396873230975882215128049713559849427311798959652681930663843994067353808298002406164092996533923220683447265882968239141724624870704231013642255563984374257471112743917655991279898690480703935007493906644744151022265929975993911186879561257100479593516979735117799410600147341193819147290056586421994333004992422258618475766549646258761885662783430625 ** 2
for i in range(x, x+2):
print(i, isSquare(i))
1000399717477066534083185452789672211951514938424998708930175541558932213310056978758103599452364409903384901149641614494249195605016959576235097480592396214296565598519295693079257885246632306201885850365687426564365813280963724310434494316592041592681626416195491751015907716210235352495422858432792668507052756279908951163972960239286719854867504108121432187033786444937064356645218196398775923710931242852937602515835035177768967470757847368349565128635934683294155947532322786360581473152034468071184081729335560769488880138928479829695277968766082973795720937033019047838250608170693879209655321034310764422462828792636246742456408134706264621790736361118589122797268261542115823201538743148116654378511916000714911467547209475246784887830649309238110794938892491396597873160778553131774466638923135932135417900066903068192088883207721545109720968467560224268563643820599665232314256575428214983451466488658896488012211237139254674708538347237589290497713613898546363590044902791724541048198769085430459186735166233549186115282574626012296888817453914112423361525305960060329430234696000121420787598967383958525670258016851764034555105019265380321048686563527396844220047826436035333266263375049097675787975100014823583097518824871586828195368306649956481108708929669583308777347960115138098217676704862934389659753628861667169905594181756523762369645897154232744410732552956489694024357481100742138381514396851789639339362228442689184910464071202445106084939268067445115601375050153663645294106475257440167535462278022649865332161044187890625 True
1000399717477066534083185452789672211951514938424998708930175541558932213310056978758103599452364409903384901149641614494249195605016959576235097480592396214296565598519295693079257885246632306201885850365687426564365813280963724310434494316592041592681626416195491751015907716210235352495422858432792668507052756279908951163972960239286719854867504108121432187033786444937064356645218196398775923710931242852937602515835035177768967470757847368349565128635934683294155947532322786360581473152034468071184081729335560769488880138928479829695277968766082973795720937033019047838250608170693879209655321034310764422462828792636246742456408134706264621790736361118589122797268261542115823201538743148116654378511916000714911467547209475246784887830649309238110794938892491396597873160778553131774466638923135932135417900066903068192088883207721545109720968467560224268563643820599665232314256575428214983451466488658896488012211237139254674708538347237589290497713613898546363590044902791724541048198769085430459186735166233549186115282574626012296888817453914112423361525305960060329430234696000121420787598967383958525670258016851764034555105019265380321048686563527396844220047826436035333266263375049097675787975100014823583097518824871586828195368306649956481108708929669583308777347960115138098217676704862934389659753628861667169905594181756523762369645897154232744410732552956489694024357481100742138381514396851789639339362228442689184910464071202445106084939268067445115601375050153663645294106475257440167535462278022649865332161044187890626 False
Dies kann mit Hilfe gelöst werden der decimal Modul beliebiger Genauigkeit Quadratwurzeln erhalten und einfache Kontrollen für „Genauigkeit“:
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]
Zur Demonstration mit wirklich großen Werten:
# 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
Wenn Sie die Größe des Wertes erhöhen getestet, dies wird schließlich ziemlich langsam (dauert die Nähe einer Sekunde für einen 200.000-Bit-Platz), aber für moderatere Zahlen (etwa 20.000 Bits), ist es immer noch schneller als ein Mensch bemerken würde für einzelne Werte (~ 33 ms auf meinem Rechner). Aber da die Geschwindigkeit nicht das primäre Anliegen war, ist dies ein guter Weg, um es mit Python Standard-Bibliotheken zu tun.
Natürlich wäre es viel schneller verwenden gmpy2 und nur Test gmpy2.mpz(x).is_square(), aber wenn Pakete von Drittanbietern sind nicht Ihre Sache ist, die oben genannten Arbeiten ganz gut.
Ich habe gerade gebucht eine leichte Variation auf einige der Beispiele oben auf einem anderen Thread ( Finding perfekte Quadrate ) und dachte, dass ich eine leichte Variation umfassen würde, was ich gepostet es hier (nsqrt als temporäre Variable) verwendet wird, falls es von Interesse / Nutzung:
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)
Es ist nicht richtig für eine große nicht-Platz wie 152415789666209426002111556165263283035677490.
Meine Antwort lautet:
def is_square(x):
return x**.5 % 1 == 0
Es hat im Grunde eine Quadratwurzel modulo dann um 1 den ganzzahligen Teil strippen, und wenn das Ergebnis 0 return True sonst False zurückzukehren. In diesem Fall x kann jede große Zahl sein, nur nicht so groß ist wie die maximale Anzahl Schwimmer, dass Python verarbeiten kann: 1.7976931348623157e + 308
Es ist nicht richtig für eine große nicht-Platz wie 152415789666209426002111556165263283035677490.
Das ist meine Methode:
def is_square(n) -> bool:
return int(n**0.5)**2 == int(n)
Nehmen Sie Quadratwurzel Nummer. Konvertieren in integer. Nehmen Sie den Platz. Wenn die Zahlen gleich sind, dann ist es ein perfektes Quadrat sonst nicht.
Es ist nicht richtig für einen großen Platz wie 152415789666209426002111556165263283035677489.
Sie können für die abgerundete Quadratwurzel binär suchen. Quadrat um das Ergebnis zu sehen, ob es den ursprünglichen Wert übereinstimmt.
Du bist wahrscheinlich besser dran mit FogleBirds Antwort - obwohl passen sie auf, als arithmetische Gleitkomma annähernd ist, was diesen Ansatz abwerfen kann. Sie könnten ein falsch positive aus einer großen Zahl im Prinzip erhalten, die man mehr als ein perfekter Platz, zum Beispiel aufgrund verlorener Präzision.
- Entscheiden Sie, wie lange die Zahl sein wird.
- nimmt ein Delta ,000000000000 ....... 000001
- sehen, ob die (sqrt (x)) ^ 2 -. X größer / gleich / kleiner als Delta und entscheiden, basierend auf den Delta-Fehlern
Diese Antwort beziehe sich nicht auf Ihre erklärte Frage, aber auf eine implizite Frage, die ich im Code sehen Sie auf dem Laufendes, das heißt, „wie zu überprüfen, ob etwas eine ganze Zahl ist?“
Die erste Antwort, die Sie im Allgemeinen auf diese Frage zu bekommen ist „Bloß nicht!“ Und es ist wahr, dass in Python, Typprüfung ist in der Regel nicht das Richtige zu tun.
Für die seltenen Ausnahmen, aber statt der Suche nach einem Komma in der Stringdarstellung der Zahl, um die Sache ist, verwenden Sie die isinstance Funktion:
>>> isinstance(5,int)
True
>>> isinstance(5.0,int)
False
Natürlich gilt dies für die Variable eher als ein Wert. Wenn ich wollte, um zu bestimmen, ob der Wert war eine ganze Zahl, würde ich dies tun:
>>> x=5.0
>>> round(x) == x
True
Aber wie alle anderen im Detail behandelt hat, gibt es Gleitkommazahlen Probleme in den meisten Nicht-Spielzeug Beispiele für diese Art von Dingen in Betracht gezogen werden.
Wenn Sie über einen Bereich in einer Schleife wollen und tun etwas für jede Zahl, die nicht ein perfektes Quadrat ist, Sie so etwas tun könnte:
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
Wenn Sie etwas für jede Zahl tun mögen, die ein perfekter Platz, der Generator ist noch einfacher:
(n * n for n in range(upper))
Ich denke, dass das funktioniert und ist sehr einfach:
import math
def is_square(num):
sqrt = math.sqrt(num)
return sqrt == int(sqrt)
Es ist nicht richtig für eine große nicht-Platz wie 152415789666209426002111556165263283035677490.
import math
def is_square(n):
sqrt = math.sqrt(n)
return sqrt == int(sqrt)
Es ist immer für einen großen nicht-Platz wie 152415789666209426002111556165263283035677490.
