webentwicklung-frage-antwort-db.com.de

Python: Prüfen Sie, ob eine Zahl ein perfektes Quadrat ist

Wie kann ich überprüfen, ob eine Zahl ein perfektes Quadrat ist?

Geschwindigkeit ist im Moment kein Problem, nur arbeiten.

64
delete

Das Problem bei der Verwendung von Gleitkommaberechnungen (math.sqrt(x) oder x**0.5) besteht darin, dass Sie nicht wirklich sicher sein können, ob diese genau sind (für ausreichend große ganze Zahlen x ist dies nicht der Fall und könnte sogar überlaufen). Zum Glück (wenn man es nicht eilig hat ;-) gibt es viele rein 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 die Quadratwurzel, siehe Wikipedia . Es funktioniert für jede positive Zahl, für die Sie genügend Speicher haben, damit die Berechnung abgeschlossen werden kann ;-).

Bearbeiten : 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 Gleitkommazwischenergebnissen basieren, vergewissern Sie sich, dass diese in diesem einfachen Beispiel korrekt funktionieren - es ist nicht so schwer (Sie brauchen nur) Ein paar zusätzliche Überprüfungen, falls das berechnete sqrt ein wenig abweicht, sind nur ein wenig vorsichtig.

Und dann versuche es mit x**7 und finde einen klugen Weg, um das Problem zu umgehen, das du bekommst.

OverflowError: long int too large to convert to float

sie müssen immer schlauer werden, wenn die Zahlen natürlich weiter steigen.

Wenn ich in Eile wäre, 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 so einfach, dass es sich wie Schummeln anfühlt (ein bisschen so, wie ich es mit Python im Allgemeinen tue ;-) - überhaupt keine Klugheit, nur perfekte Direktheit und Einfachheit (und im Fall von gmpy, pure Geschwindigkeit; -) ...

106
Alex Martelli

Verwenden Sie die Newton-Methode, um schnell auf die nächste ganzzahlige Quadratwurzel zuzugreifen, quadrieren Sie sie und sehen Sie, ob es Ihre Zahl ist. Siehe isqrt .

27
James K Polk

Da Sie sich bei Fließkommaberechnungen (wie diese Berechnungsmethoden für die Quadratwurzel) nicht auf exakte Vergleiche verlassen können, wäre die Implementierung weniger fehleranfällig

import math
def is_square(integer):
    root = math.sqrt(integer)
    if int(root + 0.5) ** 2 == integer: 
        return True
    else:
        return False

Stellen Sie sich vor, integer ist 9. math.sqrt(9) könnte 3.0 sein, aber es könnte auch etwas wie 2.99999 oder 3.00001 sein. Das Quadrieren des Ergebnisses ist also nicht zuverlässig. Wenn wir wissen, dass int den Floor-Wert annimmt, bedeutet das Erhöhen des Float-Werts um 0.5 zuerst, dass wir den gewünschten Wert erhalten, wenn wir uns in einem Bereich befinden, in dem float noch eine ausreichende Auflösung hat, um Zahlen in der Nähe des Werts darzustellen, für den der Wert steht wir schauen.

14
Mike Graham
import math
if (math.sqrt(number)-int(math.sqrt(number))):
    print "it's not a perfect square"

Ein perfektes Quadrat ist eine Zahl, die als Produkt zweier gleichartiger Ganzzahlen ausgedrückt werden kann. math.sqrt(number) gibt eine float zurück. int(math.sqrt(number)) wandelt das Ergebnis in int um.

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

11
0xPwn

Wenn Sie interessiert sind, habe ich eine rein mathematische Antwort auf eine ähnliche Frage unter Stapelaustausch Mathematik, "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 verglichen usw., um wirklich mit dieser Methode zu klicken. Ich mag ihre Einfachheit und Effizienz. Ich Habe ich 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. Ansonsten hat es keinen Sinn. Es lässt 0 als True durchrutschen (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 mit Potenzen von 4 verkleinert wurde. Dies reduziert die Größe der Zahl, mit der wir arbeiten, und beschleunigt die babylonische Methode, macht aber auch andere Prüfungen schneller.

Der dritte Codeblock führt einen einfachen Booleschen Bitlogiktest durch. Die niedrigstwertigen drei Ziffern eines perfekten Quadrats in Binärform sind 001. Immer. Speichern Sie für führende Nullen, die sich aus Potenzen von 4 ergeben, die bereits berücksichtigt wurden. Wenn der Test fehlschlägt, wissen Sie sofort, dass es sich nicht um ein Quadrat handelt. Wenn es geht, können Sie nicht sicher sein.

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

Wie der dritte Block testet der vierte den Ein-Stellen-Wert mit einem einfachen Moduloperator als Dezimalzahl und tendiert dazu, Werte abzufangen, die durch den vorherigen Test verrutschen. Ebenfalls 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, werden durch 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 überflüssig waren oder nie tatsächlich verwendet wurden.

Schließlich ähnelt der sechste Codeblock stark der Antwort von Alex Martelli. Grundsätzlich wird die Quadratwurzel mit dem alten babylonischen Algorithmus gefunden, aber unter Ignorierung von Gleitkommazahlen auf ganzzahlige Werte beschränkt. Dies gilt sowohl für die Geschwindigkeit als auch für die Erweiterung der Werte, die getestet werden können. Ich habe Mengen anstelle von Listen verwendet, da dies viel weniger Zeit in Anspruch nimmt, ich habe Bitverschiebungen anstelle der Division durch zwei verwendet und ich habe einen Anfangswert viel effizienter gewählt.

Übrigens habe ich Alex Martellis empfohlene Testnummer sowie einige Zahlen getestet, die um ein Vielfaches 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 genauso wie der von Alex Martelli, mit allen Vorteilen, aber dem zusätzlichen Vorteil, dass hocheffiziente Ablehnungen von einfachen Tests viel Zeit sparen, ganz zu schweigen von der Reduzierung der Testanzahl durch Potenzen von 4, was die Geschwindigkeit, Effizienz, Genauigkeit und die Größe der zu testenden Zahlen verbessert. Wahrscheinlich besonders bei Nicht-Python-Implementierungen.

Etwa 99% aller Ganzzahlen werden als nicht quadratisch zurückgewiesen, bevor die babylonische Wurzelextraktion überhaupt implementiert wird, und in 2/3 der Zeit, die das babylonische System benötigt, um die Ganzzahl zurückzuweisen. Und obwohl diese Tests den Prozess nicht wesentlich beschleunigen, beschleunigt die Reduzierung aller Testzahlen auf eine ungerade, indem alle Potenzen von 4 geteilt werden , den Babylonier wirklich Prüfung.

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) brauchte ich für Surface 3 durchschnittlich 165 Sekunden (mit 100% iger Genauigkeit). Mit nur den logischen Tests in meinem Algorithmus (mit Ausnahme des Babylonischen) dauerte es 127 Sekunden, und 99% aller Ganzzahlen wurden als nicht quadratisch zurückgewiesen, ohne dass versehentlich perfekte Quadrate zurückgewiesen wurden. Von diesen ganzen Zahlen, die bestanden, 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. Der Test 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, den Datentyp und die Positivität zu überprüfen. Beseitigen Sie die ersten beiden Überprüfungen, und ich habe das Experiment um eine Minute gekürzt. Man muss davon ausgehen, dass der Benutzer klug genug ist, um zu wissen, dass Negative und Floats keine perfekten Quadrate sind.

8

Ich bin neu bei Stack Overflow und habe kurz nach einer Lösung gesucht. Ich habe gerade eine kleine Variation zu einigen der obigen Beispiele in einem anderen Thread ( Suche nach perfekten Quadraten ) veröffentlicht und dachte, ich würde eine geringfügige Variation dessen hinzufügen, was ich hier gepostet habe (unter Verwendung von nsqrt als temporäre Variable) es ist von Interesse/Nutzen:

import math

def is_perfect_square(n):
  if not ( isinstance(n, (int, long)) and ( n >= 0 ) ):
    return False 
  else:
    nsqrt = math.sqrt(n)
    return nsqrt == math.trunc(nsqrt)
6
gumption

Dies kann mit dem Modul decimal gelöst werden, um beliebige Quadratwurzeln mit beliebiger Genauigkeit und einfache Überprüfung 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 zu testenden Wert vergrößern, wird dieser Wert möglicherweise etwas langsamer (für ein 200.000-Bit-Quadrat dauert es fast eine Sekunde), bei moderaten Zahlen (z. B. 20.000 Bit) ist dies jedoch immer noch schneller, als ein Mensch dies bemerken würde Einzelwerte (~ 33 ms auf meiner Maschine). Da Geschwindigkeit jedoch nicht Ihr Hauptanliegen ist, ist dies eine gute Möglichkeit, dies mit Pythons Standardbibliotheken zu tun.

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

4
ShadowRanger

Meine Antwort wäre:

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

Dies macht im Grunde eine Quadratwurzel, dann modulo um 1, um den ganzzahligen Teil zu entfernen. Wenn das Ergebnis 0 ist, wird True zurückgegeben, andernfalls 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

3
Lasagnenator

Sie könnten die abgerundete Quadratwurzel binär suchen. Quadrieren Sie das Ergebnis, um zu sehen, ob es mit dem ursprünglichen Wert übereinstimmt.

Mit der Antwort von FogleBirds sind Sie wahrscheinlich besser dran - aber Vorsicht, da die Fließkomma-Arithmetik nur annähernd ist, was diesen Ansatz abschrecken kann. Sie können im Prinzip ein falsch positives Ergebnis von einer großen Ganzzahl erhalten, die beispielsweise aufgrund von Genauigkeitsverlust mehr als ein perfektes Quadrat ist.

2
Steve314

Das ist meine Methode 

int(n**0.5)**2 == int(n)

nehmen Sie die Quadratwurzel der Zahl in Ganzzahl konvertieren und nehmen Sie dann das Quadrat Wenn die Zahlen gleich sind, ist es ein perfektes Quadrat, sonst nicht.

2
Archu Sm

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 ich prüfen, ob etwas eine Ganzzahl ist?"

Die erste Antwort, die Sie im Allgemeinen auf diese Frage erhalten, lautet "Nicht!" Es stimmt, dass in Python die Typüberprüfung normalerweise nicht das Richtige ist.

Für diese seltenen Ausnahmen verwenden Sie statt der Suche nach einem Dezimalpunkt in der Zeichenfolgendarstellung der Zahl die Funktion isinstance :

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

Dies gilt natürlich für die Variable und nicht 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

Da jedoch alle anderen ausführlich behandelt haben, gibt es bei den meisten Nicht-Spielzeug-Beispielen solcher Dinge Fließkomma-Probleme.

1
Vicki Laidler

Dies ist numerisch eine so naive Lösung, wie Sie möglicherweise haben können. Es funktioniert bei kleinen Stückzahlen.

def is_perfect_square(n):
    return (n ** .5).is_integer()

Offensichtlich versagt es bei einer großen Anzahl wie 152415789666209426002111556165263283035677490.

1
A-B-B

Wenn Sie einen Bereich durchlaufen und für jede Zahl etwas tun wollen, die NICHT ein 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 IS] ein perfektes Quadrat ist, etwas tun wollen, ist der Generator noch einfacher:

(n * n for n in range(upper))
1
Moberg
  1. Entscheiden Sie, wie lang die Nummer sein wird.
  2. nimm ein Delta 0.000000000000 ....... 000001
  3. prüfen Sie, ob (sqrt (x)) ^ 2 - x größer/gleich/kleiner als Delta ist, und entscheiden Sie anhand des Delta-Fehlers.

Ich denke das funktioniert und ist sehr einfach: 

from math import sqrt

def is_perfect_square(num):
    return int(sqrt(num)) == sqrt(num)
1
a = math.sqrt(n)
b = int(a) 
a == b 
0

Ich bin mir der Python nicht sicher, aber Sie könnten so etwas tun:

function isSquare(x) = x == floor(sqrt(x) + 0.5)^2

Nehmen Sie also eine Zahl, suchen Sie nach der Quadratwurzel, runden Sie sie auf die nächste Ganzzahl ab, quadrieren Sie sie und testen Sie, ob sie der ursprünglichen Zahl entspricht. (floor und das Hinzufügen von 0.5 wird durchgeführt, um zu verhindern, dass sqrt(4)1.9999999... aufgrund von Gleitkomma-Berechnungen zurückgegeben wird, wie Mike Graham betont hat.)

Für den Fall, dass Sie interessiert sind, gab es einmal eine sehr gute Diskussion über die Schnellste Methode, um festzustellen, ob die Quadratwurzel einer Ganzzahl eine Ganzzahl ist .

Zur Klarstellung bearbeitet.

0
David Johnstone