Überprüfen Sie, ob eine Zahl ein perfektes Quadrat ist

Antworten:

114

Das Problem bei der Verwendung von Gleitkomma-Berechnungen ( math.sqrt(x)oder x**0.5) besteht darin, dass Sie nicht wirklich sicher sein können, ob sie genau sind (bei ausreichend großen Ganzzahlen xist dies nicht der Fall und kann sogar überlaufen). Zum Glück (wenn man es nicht eilig hat ;-) gibt es viele reine ganzzahlige Ansätze, wie zum Beispiel 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 basiert auf dem "babylonischen Algorithmus" für Quadratwurzel, siehe Wikipedia . Es funktioniert für jede positive Zahl, für die Sie genügend Speicher haben, damit die Berechnung abgeschlossen werden kann ;-).

Edit : sehen wir uns ein Beispiel an ...

x = 12345678987654321234567 ** 2

for i in range(x, x+2):
   print i, is_square(i)

dies druckt wie gewünscht (und in angemessener Zeit auch ;-):

152415789666209426002111556165263283035677489 True
152415789666209426002111556165263283035677490 False

Bevor Sie Lösungen vorschlagen, die auf Gleitkomma-Zwischenergebnissen basieren, stellen Sie bitte sicher, dass sie in diesem einfachen Beispiel korrekt funktionieren - es ist nicht so schwer (Sie benötigen nur ein paar zusätzliche Überprüfungen, falls das berechnete Quadrat etwas abweicht) ein bisschen Sorgfalt.

Und dann versuchen Sie es mit x**7und finden Sie einen cleveren Weg, um das Problem zu umgehen, das Sie bekommen werden.

OverflowError: long int too large to convert to float

Sie müssen immer klüger werden, da die Zahlen natürlich weiter wachsen.

Wenn ich es eilig hätte, würde ich natürlich gmpy verwenden - 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 einfach so einfach, dass es sich wie Betrug anfühlt (ein bisschen so, wie ich mich generell gegenüber Python fühle ;-) - überhaupt keine Klugheit, nur perfekte Direktheit und Einfachheit (und im Fall von gmpy reine Geschwindigkeit ; -) ...

Alex Martelli
quelle
Sagen Sie, was Sie über den Autor wollen, gmpy klingt nach einem großartigen Werkzeug für diese Aufgabe.
Mike Graham
2
Die babylonische Methode funktioniert gut, aber Sie müssen Sonderfälle für 0 und 1 haben, um eine Division durch Null zu vermeiden.
Mpenkov
2
Übrigens set([x])={x}
Oscar Mederos
6
Ist das nicht setovekill? Konvergiert Babylonian nicht einfach dahin int(sqrt(x)), wo wir nur prüfen müssen, ob prev != next?
Tomasz Gandor
1
"Ich weiß, das ist einfach so einfach, dass es sich wie Betrug anfühlt (ein bisschen wie ich mich Python gegenüber im Allgemeinen fühle". Soo wahr;)
Arulx Z
37

Verwenden Sie die Newton-Methode, um schnell die nächste ganzzahlige Quadratwurzel zu ermitteln, sie dann zu quadrieren und festzustellen, ob es sich um Ihre Zahl handelt. Siehe isqrt .

Python ≥ 3.8 hat math.isqrt. Wenn eine ältere Version von Python, suchen Sie nach der „ def isqrt(n)“ Implementierung hier .

import math

def is_square(i: int) -> bool:
    return i == math.isqrt(i) ** 2
Präsident James K. Polk
quelle
20

Da Sie sich bei Gleitkommaberechnungen (wie diesen Methoden zur Berechnung der Quadratwurzel) niemals auf genaue Vergleiche verlassen können, wäre eine weniger fehleranfällige Implementierung

import math

def is_square(integer):
    root = math.sqrt(integer)
    return integer == int(root + 0.5) ** 2

Stellen Sie sich vor, integerist 9. math.sqrt(9)könnte sein 3.0, aber es könnte auch so etwas wie 2.99999oder sein 3.00001, daher ist es nicht zuverlässig, das Ergebnis sofort zu quadrieren. Wenn wir wissen, dass dies intden Mindestwert erfordert, erhalten 0.5wir den gewünschten Wert, wenn wir uns in einem Bereich befinden, in dem die floatAuflösung noch fein genug ist, um Zahlen in der Nähe der gesuchten darzustellen .

Mike Graham
quelle
4
Es wäre etwas besser, if int(root + 0.5) ** 2 == integer:wenn wir uns intwie floorfür die Zahlen verhalten, die uns wichtig sind.
David Johnstone
@ David Johnstone, ich habe diesen Beitrag geändert, um diese Implementierung zu verwenden. Ich bin damit einverstanden, dass sie besser ist als die alte Art, die ich hatte. In jedem Fall sind einige der anderen Techniken, die andere hier erwähnen, noch besser und zuverlässiger.
Mike Graham
Ich verstehe, dass FP ungefähr ist, aber math.sqrt(9)wirklich jemals sein kann 2.99999? Pythons floatKarten sind Cs zugeordnet double, aber ich denke, sogar ein 16-Bit-FP-Typ hat eine höhere Genauigkeit. Wenn Sie also einen C-Compiler hätten, der 8-Bit-FP ("Minifloats") als doubleTyp verwendet? Ich nehme an, es ist technisch möglich, aber es scheint mir unwahrscheinlich, dass dies auf jedem Computer der Fall ist, auf dem heute Python ausgeführt wird.
Ken
@ Ken, ich sagte "so etwas wie", um anzuzeigen, dass ich zum zugrunde liegenden Konzept komme; Es kann nicht garantiert werden, dass der Wert, den Sie erhalten, nicht geringfügig unter dem genauen Wert liegt. Ich kann mir nicht vorstellen , dass math.sqrt(9)zurückkehren wird 2.99999an einem bestimmten System, aber das tatsächliche Ergebnis ist systemabhängig und kann nicht genau sein erwarten.
Mike Graham
Entschuldigung, ich habe "Gefällt mir" als "zum Beispiel" und nicht als "in der Nachbarschaft" verstanden. Ein weiteres Opfer des Krieges zwischen Englisch und Mathematik!
Ken
12

Wenn Sie interessiert sind, habe ich eine rein mathematische Antwort auf eine ähnliche Frage bei math stackexchange: "Perfekte Quadrate schneller erkennen als durch Extrahieren der Quadratwurzel" .

Meine eigene Implementierung von isSquare (n) ist vielleicht nicht die beste, aber ich mag es. Ich habe mehrere Monate in Mathe-Theorie, digitaler Berechnung und Python-Programmierung studiert und mich mit anderen Mitwirkenden usw. verglichen, um wirklich mit dieser Methode zu klicken. Ich mag seine Einfachheit und Effizienz. Ich habe nicht besser gesehen. Sag mir was du denkst.

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 einfach. Zuerst wird überprüft, ob wir eine Ganzzahl haben, und zwar eine positive. Sonst hat es keinen Sinn. Es lässt 0 als True durch (notwendig oder der nächste Block ist eine Endlosschleife).

Der nächste Codeblock entfernt systematisch Potenzen von 4 in einem sehr schnellen Subalgorithmus unter Verwendung von Bitverschiebungs- und Bitlogikoperationen. Wir finden letztendlich nicht das isSquare unseres ursprünglichen n, sondern eines k <n, das nach Möglichkeit um Potenzen von 4 verkleinert wurde. Dies reduziert die Größe der Zahl, mit der wir arbeiten, und beschleunigt die babylonische Methode erheblich, beschleunigt aber auch andere Überprüfungen.

Der dritte Codeblock führt einen einfachen booleschen Bitlogiktest durch. Die niedrigstwertigen drei binären Ziffern eines perfekten Quadrats sind 001. Immer. Außer für führende Nullen, die sich ohnehin aus Potenzen von 4 ergeben, die bereits berücksichtigt wurden. Wenn der Test nicht bestanden wird, wissen Sie sofort, dass es sich nicht um ein Quadrat handelt. Wenn es vorbei ist, können Sie nicht sicher sein.

Wenn wir für einen Testwert eine 1 erhalten, war die Testnummer ursprünglich eine Potenz von 4, einschließlich vielleicht 1 selbst.

Wie der dritte Block testet der vierte den Einstellenwert in Dezimalzahl unter Verwendung eines einfachen Moduloperators und neigt dazu, Werte zu erfassen, die durch den vorherigen Test rutschen. Auch ein Mod 7, Mod 8, Mod 9 und Mod 13 Test.

Der fünfte Codeblock sucht nach einigen der bekannten perfekten quadratischen Muster. Zahlen, die mit 1 oder 9 enden, wird ein Vielfaches von vier vorangestellt. Und Zahlen, die mit 5 enden, müssen mit 5625, 0625, 225 oder 025 enden. Ich hatte andere eingeschlossen, aber festgestellt, dass sie redundant waren oder nie tatsächlich verwendet wurden.

Schließlich ähnelt der sechste Codeblock sehr der Antwort des Top-Antworters - Alex Martelli -. Findet die Quadratwurzel im Grunde genommen unter Verwendung des alten babylonischen Algorithmus, beschränkt sie jedoch auf ganzzahlige Werte, während Gleitkommawerte ignoriert werden. Dies gilt sowohl für die Geschwindigkeit als auch für die Erweiterung der Größen von Werten, die getestet werden können. Ich habe Mengen anstelle von Listen verwendet, weil es viel weniger Zeit in Anspruch nimmt, ich habe Bitverschiebungen anstelle von Division durch zwei verwendet und ich habe einen anfänglichen Startwert viel effizienter gewählt.

Übrigens habe ich die von Alex Martelli empfohlene Testnummer sowie einige Zahlen getestet, die um viele Größenordnungen größer sind, wie zum Beispiel:

x=1000199838770766116385386300483414671297203029840113913153824086810909168246772838680374612768821282446322068401699727842499994541063844393713189701844134801239504543830737724442006577672181059194558045164589783791764790043104263404683317158624270845302200548606715007310112016456397357027095564872551184907513312382763025454118825703090010401842892088063527451562032322039937924274426211671442740679624285180817682659081248396873230975882215128049713559849427311798959652681930663843994067353808298002406164092996533923220683447265882968239141724624870704231013642255563984374257471112743917655991279898690480703935007493906644744151022265929975993911186879561257100479593516979735117799410600147341193819147290056586421994333004992422258618475766549646258761885662783430625 ** 2
for i in range(x, x+2):
    print(i, isSquare(i))

druckte die folgenden Ergebnisse:

1000399717477066534083185452789672211951514938424998708930175541558932213310056978758103599452364409903384901149641614494249195605016959576235097480592396214296565598519295693079257885246632306201885850365687426564365813280963724310434494316592041592681626416195491751015907716210235352495422858432792668507052756279908951163972960239286719854867504108121432187033786444937064356645218196398775923710931242852937602515835035177768967470757847368349565128635934683294155947532322786360581473152034468071184081729335560769488880138928479829695277968766082973795720937033019047838250608170693879209655321034310764422462828792636246742456408134706264621790736361118589122797268261542115823201538743148116654378511916000714911467547209475246784887830649309238110794938892491396597873160778553131774466638923135932135417900066903068192088883207721545109720968467560224268563643820599665232314256575428214983451466488658896488012211237139254674708538347237589290497713613898546363590044902791724541048198769085430459186735166233549186115282574626012296888817453914112423361525305960060329430234696000121420787598967383958525670258016851764034555105019265380321048686563527396844220047826436035333266263375049097675787975100014823583097518824871586828195368306649956481108708929669583308777347960115138098217676704862934389659753628861667169905594181756523762369645897154232744410732552956489694024357481100742138381514396851789639339362228442689184910464071202445106084939268067445115601375050153663645294106475257440167535462278022649865332161044187890625 True
1000399717477066534083185452789672211951514938424998708930175541558932213310056978758103599452364409903384901149641614494249195605016959576235097480592396214296565598519295693079257885246632306201885850365687426564365813280963724310434494316592041592681626416195491751015907716210235352495422858432792668507052756279908951163972960239286719854867504108121432187033786444937064356645218196398775923710931242852937602515835035177768967470757847368349565128635934683294155947532322786360581473152034468071184081729335560769488880138928479829695277968766082973795720937033019047838250608170693879209655321034310764422462828792636246742456408134706264621790736361118589122797268261542115823201538743148116654378511916000714911467547209475246784887830649309238110794938892491396597873160778553131774466638923135932135417900066903068192088883207721545109720968467560224268563643820599665232314256575428214983451466488658896488012211237139254674708538347237589290497713613898546363590044902791724541048198769085430459186735166233549186115282574626012296888817453914112423361525305960060329430234696000121420787598967383958525670258016851764034555105019265380321048686563527396844220047826436035333266263375049097675787975100014823583097518824871586828195368306649956481108708929669583308777347960115138098217676704862934389659753628861667169905594181756523762369645897154232744410732552956489694024357481100742138381514396851789639339362228442689184910464071202445106084939268067445115601375050153663645294106475257440167535462278022649865332161044187890626 False

Und das in 0,33 Sekunden.

Meiner Meinung nach funktioniert mein Algorithmus mit allen Vorteilen genauso wie der von Alex Martelli, hat jedoch den zusätzlichen Vorteil hocheffizienter Ablehnungen bei einfachen Tests, die viel Zeit sparen, ganz zu schweigen von der Verringerung der Größe der Testnummern um Potenzen von 4, die Geschwindigkeit, Effizienz, Genauigkeit und die Größe der überprüfbaren Zahlen verbessert. Wahrscheinlich besonders in Nicht-Python-Implementierungen.

Ungefähr 99% aller ganzen Zahlen werden als nicht quadratisch abgelehnt, bevor die babylonische Wurzelextraktion überhaupt implementiert wird, und in 2/3 der Zeit, die der babylonische benötigt, um die ganze Zahl abzulehnen. Und obwohl diese Tests den Prozess nicht wesentlich beschleunigen, beschleunigt die Reduzierung aller Testzahlen auf eine ungerade durch Aufteilen aller Potenzen von 4 den babylonischen Test wirklich .

Ich habe einen Zeitvergleichstest gemacht. Ich habe alle ganzen Zahlen von 1 bis 10 Millionen nacheinander getestet. Mit der babylonischen Methode allein (mit meiner speziell zugeschnittenen anfänglichen Vermutung) dauerte meine Oberfläche 3 durchschnittlich 165 Sekunden (mit 100% Genauigkeit). Mit nur den logischen Tests in meinem Algorithmus (mit Ausnahme des Babylonischen) dauerte es 127 Sekunden. 99% aller ganzen Zahlen wurden als Nicht-Quadrat zurückgewiesen, ohne versehentlich perfekte Quadrate abzulehnen. Von diesen ganzen Zahlen waren nur 3% perfekte Quadrate (eine viel höhere Dichte). Unter Verwendung des obigen vollständigen Algorithmus, der sowohl die logischen Tests als auch die babylonische Wurzelextraktion verwendet, haben wir eine 100% ige Genauigkeit und einen Testabschluss in nur 14 Sekunden. Das Testen der ersten 100 Millionen Ganzzahlen dauert ungefähr 2 Minuten und 45 Sekunden.

EDIT: Ich konnte die Zeit weiter verkürzen. Ich kann jetzt die ganzen Zahlen 0 bis 100 Millionen in 1 Minute 40 Sekunden testen. Es wird viel Zeit verschwendet, um den Datentyp und die Positivität zu überprüfen. Beseitigen Sie die ersten beiden Überprüfungen und ich habe das Experiment um eine Minute verkürzt. Man muss davon ausgehen, dass der Benutzer klug genug ist, um zu wissen, dass Negative und Floats keine perfekten Quadrate sind.

CogitoErgoCogitoSum
quelle
Der Einfachheit halber ist es schwer, die akzeptierte Antwort zu übertreffen. In Bezug auf die Leistung sollte Ihre besser sein. Ich bin skeptisch, wie wichtig es ist, das Ziel durch quadratische Potenzen kleiner Primzahlen zu reduzieren, aber die Berechnung von Jacobi-Symbolen für kleine Primzahlen sollte ein Gewinn sein. Und je größer die Zahlen, desto größer der Vorteil dieser Antwort.
Präsident James K. Polk
1
Für die Berechnung des Jacobi-Symbols ist eine Reduzierung der Potenzen kleiner Primzahlen erforderlich, um deterministische Ergebnisse zu erzielen. Andernfalls ist es bestenfalls probabilistisch oder deterministisch für Nicht-Rechtwinkligkeit, überprüft jedoch nicht die Rechtwinkligkeit. Das ist teilweise der Grund, warum ich nach Potenzen von Quadraten faktorisiere; Die einzigen Jacobi-Symbole, die ich berechne, sind für dieselben kleinen Primzahlen, die ich herausrechne. Ich mache es auch einfach, um die Größe der Testnummer zu reduzieren, um die später verwendete babylonische Methode etwas schneller zu machen (aber das ist umstritten).
CogitoErgoCogitoSum
Nun, es ist sicherlich eine gute und einzigartige Antwort, und wenn ich in der Zukunft etwas Zeit habe, möchte ich damit herumspielen, versuchen Sie einige Timings, die die Anzahl der kleinen Primzahlen variieren, um zu sehen, ob bei einer bestimmten Bitgröße eine optimale Anzahl gefunden werden kann .
Präsident James K. Polk
Testen Sie auf jeden Fall meinen Code. Mach es kaputt. Ich bin kein Programmierer von Beruf, ich bin ein Mathe-Major. Python ist nur ein Hobby. Ich wäre gespannt, ob es im Durchschnitt effizienter ist.
CogitoErgoCogitoSum
1
Wenn Sie immer noch da drin interessiert sind , ist im Wesentlichen eine doppelte Frage hier mit einigen interessanten Antworten, vor allem A.Rex Antwort .
Präsident James K. Polk
11
import math

def is_square(n):
    sqrt = math.sqrt(n)
    return (sqrt - int(sqrt)) == 0

Ein perfektes Quadrat ist eine Zahl, die als Produkt zweier gleicher Ganzzahlen ausgedrückt werden kann. math.sqrt(number)Rückgabe a float. int(math.sqrt(number))wirft das Ergebnis auf int.

Wenn die Quadratwurzel eine ganze Zahl ist, wie zum Beispiel 3, dann math.sqrt(number) - int(math.sqrt(number))ist 0 und die ifAnweisung ist False. Wenn die Quadratwurzel eine reelle Zahl wie 3,2 war, wird sie Truegedruckt und "es ist kein perfektes Quadrat" gedruckt.

Bei einem großen Nichtquadrat wie 152415789666209426002111556165263283035677490 schlägt dies fehl.

0xPwn
quelle
Wechseln Sie if (math.sqrt(number)-int(math.sqrt(number))):zu einer a=math.sqrt(number)anderen Zeile für : if a-int(a):. Dies liegt daran, dass die Quadratwurzel nur einmal berechnet werden muss, was imo für großes n von Bedeutung ist
unseen_rider
@ JamesKPolk Warum ist das so?
user1717828
5

Dies kann mithilfe des decimalModuls gelöst werden , um Quadratwurzeln mit beliebiger Genauigkeit und einfache Überprüfungen auf "Genauigkeit" zu erhalten:

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 den getesteten Wert vergrößern, wird dies schließlich ziemlich langsam (dauert bei einem 200.000-Bit-Quadrat fast eine Sekunde), bei moderateren Zahlen (z. B. 20.000 Bit) ist es jedoch immer noch schneller, als ein Mensch es bemerken würde Einzelwerte (~ 33 ms auf meiner Maschine). Da Geschwindigkeit jedoch nicht Ihr Hauptanliegen war, ist dies eine gute Möglichkeit, dies mit den Standardbibliotheken von Python zu tun.

Natürlich wäre es viel schneller zu verwenden gmpy2und nur zu testen gmpy2.mpz(x).is_square(), aber wenn Pakete von Drittanbietern nicht Ihr Ding sind, funktioniert das oben genannte ziemlich gut.

ShadowRanger
quelle
5

Ich habe gerade eine geringfügige Abweichung von einigen der obigen Beispiele in einem anderen Thread veröffentlicht ( Finden perfekter Quadrate ) und dachte, ich würde eine geringfügige Abweichung von dem, was ich hier veröffentlicht habe, einfügen (wobei nsqrt als temporäre Variable verwendet wird), falls dies von Interesse ist. verwenden:

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 falsch für ein großes Nichtquadrat wie 152415789666209426002111556165263283035677490.

Grips
quelle
5

Meine Antwort lautet:

def is_square(x):
    return x**.5 % 1 == 0

Es macht im Grunde eine Quadratwurzel, dann modulo um 1, um den ganzzahligen Teil zu entfernen, und wenn das Ergebnis 0 ist, geben Sie es zurück, Trueandernfalls geben Sie es zurück False. In diesem Fall kann x eine beliebige große Zahl sein, nur nicht so groß wie die maximale Float-Zahl, die Python verarbeiten kann: 1.7976931348623157e + 308

Es ist falsch für ein großes Nichtquadrat wie 152415789666209426002111556165263283035677490.

Lasagnenator
quelle
2

Das ist meine Methode:

def is_square(n) -> bool:
    return int(n**0.5)**2 == int(n)

Nimm die Quadratwurzel der Zahl. In eine Ganzzahl konvertieren. Nimm den Platz. Wenn die Zahlen gleich sind, ist es ein perfektes Quadrat, sonst nicht.

Es ist falsch für ein großes Quadrat wie 152415789666209426002111556165263283035677489.

Archu Sm
quelle
Funktioniert nicht für negative Zahlen, ist aber dennoch eine großartige Lösung!
Rick M.
1

Sie könnten binär nach der gerundeten Quadratwurzel suchen. Quadrieren Sie das Ergebnis, um festzustellen, ob es mit dem ursprünglichen Wert übereinstimmt.

Mit der Antwort von FogleBirds sind Sie wahrscheinlich besser dran - seien Sie jedoch vorsichtig, da die Gleitkomma-Arithmetik ungefähr ist, was diesen Ansatz beeinträchtigen kann. Sie könnten im Prinzip ein falsches Positiv aus einer großen Ganzzahl erhalten, die mehr als ein perfektes Quadrat ist, beispielsweise aufgrund von Genauigkeitsverlusten.

Steve314
quelle
0
  1. Entscheiden Sie, wie lang die Nummer sein soll.
  2. Nehmen Sie ein Delta 0,000000000000 ....... 000001
  3. Überprüfen Sie, ob (sqrt (x)) ^ 2 - x größer / gleich / kleiner als Delta ist, und entscheiden Sie anhand des Delta-Fehlers.
Cezar Alexandru Vancea
quelle
0

Diese Antwort bezieht sich nicht auf Ihre angegebene Frage, sondern auf eine implizite Frage, die ich in dem von Ihnen geposteten Code sehe, z. B. "Wie kann überprüft werden, ob etwas eine Ganzzahl ist?"

Die erste Antwort auf diese Frage lautet im Allgemeinen "Nicht!" Und es ist wahr, dass in Python Typchecking normalerweise nicht das Richtige ist.

Für diese seltenen Ausnahmen müssen Sie jedoch nicht nach einem Dezimalpunkt in der Zeichenfolgendarstellung der Zahl suchen, sondern die isinstance- Funktion verwenden:

>>> isinstance(5,int)
True
>>> isinstance(5.0,int)
False

Dies gilt natürlich eher für die Variable als für einen Wert. Wenn ich feststellen wollte, ob der Wert eine Ganzzahl ist, würde ich Folgendes tun:

>>> x=5.0
>>> round(x) == x
True

Aber wie alle anderen ausführlich behandelt haben, gibt es Gleitkomma-Probleme, die in den meisten Nicht-Spielzeug-Beispielen dieser Art zu berücksichtigen sind.

Vicki Laidler
quelle
1
Was bedeutet "dies gilt eher für die Variable als für einen Wert"? Sie können round (5.0) == 5.0 und isinstance (x, int) problemlos verwenden. (Und das OOWTDI soll nur x.is_integer () aufrufen.)
Veky
0

Wenn Sie einen Bereich durchlaufen und für jede Zahl etwas tun möchten, das KEIN perfektes Quadrat ist, können Sie Folgendes tun:

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 für jede Zahl, die ein perfektes Quadrat ist, etwas tun möchten, ist der Generator noch einfacher:

(n * n for n in range(upper))
Moberg
quelle
0

Ich denke, dass dies funktioniert und sehr einfach ist:

import math

def is_square(num):
    sqrt = math.sqrt(num)
    return sqrt == int(sqrt)

Es ist falsch für ein großes Nichtquadrat wie 152415789666209426002111556165263283035677490.

alejandro izquierdo
quelle
Dies ist die gleiche Antwort wie oben.
Kowalski
0

Der Rest oder der Modul der Quadratwurzel der Zahl ohne Rest bedeutet, dass es sich um ein perfektes Quadrat handelt. Modulus ist eine integrierte Funktion in allen Python-Versionen.

def is_square(num: int) -> bool:
    return num % math.sqrt(num) == 0

Ich habe dies anhand einer Liste perfekter Quadrate von bis zu 1000 überprüft.

GeneralCode
quelle
0

Eine Variante der Lösung von @Alex Martelli ohne set

Wann x in seenist True:

  • In den meisten Fällen ist es die zuletzt hinzugefügte, z. B. erzeugt 1022 die xSequenz 511, 256, 129, 68, 41, 32, 31 , 31 ;
  • In einigen Fällen (dh für die Vorgänger perfekter Quadrate) ist es das vorletzte hinzugefügte, z. B. 1023 ergibt 511, 256, 129, 68, 41, 32 , 31, 32 .

Daher reicht es aus, anzuhalten, sobald der Strom xgrößer oder gleich dem vorherigen ist:

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)

Äquivalenz mit dem ursprünglichen Algorithmus, getestet für 1 <n <10 ** 7. Im gleichen Intervall ist diese etwas einfachere Variante etwa 1,4-mal schneller.

Aristide
quelle
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')
Pemba Tamang
quelle
Obwohl dieser Code das Problem lösen könnte, sollte eine gute Antwort auch erklären, was der Code tut und wie er hilft.
BDL
0

Die Idee ist, eine Schleife von i = 1 zum Boden (sqrt (n)) zu führen und dann zu überprüfen, ob durch Quadrieren n entsteht.

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; 
} 
Pragati Verma
quelle
-3
import math

def is_square(n):
    sqrt = math.sqrt(n)
    return sqrt == int(sqrt)

Bei einem großen Nichtquadrat wie 152415789666209426002111556165263283035677490 schlägt dies fehl.

Ravi Sankar Raju
quelle
2
Dies ist eine reine Code-Antwort. Bitte geben Sie einige Gründe an.
Hotzst
Sie können Ihren Weg durch dieses @hotzst nicht begründen? Es macht vollkommen Sinn und ich bin nicht einmal ein Experte für Python. Es ist nicht der größte Test, aber er ist sowohl theoretisch als auch für kleine Fälle gültig.
CogitoErgoCogitoSum
1
@CogitoErgoCogitoSum: Du verstehst nicht. Nur-Code-Antworten werden bei Suchvorgängen mit Suchmaschinen wie Google nicht gefunden. Ob man die Antwort verstehen kann, spielt keine Rolle.
Präsident James K. Polk