Square Root (Integer)

Q: Wie hoch ist die Zeitkomplexität der binären Suche nach der Quadratwurzel?

O(log x) Zeit und O(1) Speicherplatz. In jedem Schritt wird der Bereich der möglichen Kandidaten halbiert, daher sind für x = 2^31 - 1 31 Schritte erforderlich. Von 0 an hochzuzählen dauert O(√x) Schritte, bei demselben x sind das 46340. Das ist hier in Ordnung, wächst bei 64-Bit-Eingaben aber schnell an.

Q: Wie berechnet das Newton-Verfahren eine ganzzahlige Quadratwurzel?

Beginne mit r = x . Solange r × r > x gilt, ersetze r durch (r + x / r) / 2 mit ganzzahliger Division. Bei jedem Schritt wird r in Richtung der Wurzel verringert, ohne sie zu unterschreiten, und die Schleife endet beim ganzzahligen Anteil der Quadratwurzel. Für x = 2^31 - 1 sind 19 Schritte nötig, und die Anzahl der korrekten Stellen verdoppelt sich ungefähr mit jedem Schritt, sobald der Wert nahe genug liegt.

LeichtBinäre Suche Mathe und Simulation

+10

Deine Funktion erhält eine nichtnegative Ganzzahl x und gibt ihre ganzzahlige Quadratwurzel zurück: die größte Ganzzahl r mit r × r ≤ x. Das ist die abgerundete Quadratwurzel. Bei einer Zahl, die keine Quadratzahl ist, erhältst du also die Wurzel aus der nächstkleineren Quadratzahl. Berechne sie selbst, ohne eine eingebaute Quadratwurzel- oder Potenzfunktion zu verwenden.

Funktion

mySqrt(x: integer) → integer

xinteger: die nichtnegative ganze Zahl, aus der die Quadratwurzel gezogen werden soll
Gibt zurückinteger: Die Quadratwurzel von x, abgerundet auf eine ganze Zahl

Einschränkungen

0 ≤ x ≤ 2³¹ - 1
Rufe keine eingebaute Funktion für Quadratwurzeln, Potenzen oder Exponenten auf.

Beispiele

Eingabe: x = 17
Ausgabe: 4
Erklärung: 4 × 4 = 16 ist höchstens 17, aber 5 × 5 = 25 ist mehr, also wird die Wurzel aus 17 auf 4 abgerundet.

Eingabe: x = 49
Ausgabe: 7
Erklärung: 49 ist eine Quadratzahl, 7 × 7 = 49, daher wird nichts gerundet und das Ergebnis ist genau 7.

+17 versteckte Tests beim Einreichen

Weiterführende Frage

Wie würdest du stattdessen die ganzzahlige Kubikwurzel finden, also das größte r mit r × r × r ≤ x, wenn x auch negativ sein könnte?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Von 0 an hochzuzählen, bis das nächste Quadrat größer als x ist, liefert die richtige Antwort, braucht aber einen Schritt pro Einheit der Wurzel, also nahe dem oberen Ende des Wertebereichs etwa 46000 Schritte. Die Quadratzahlen 0, 1, 4, 9, 16 und so weiter sind sortiert, daher kannst du mit einer binären Suche den letzten Kandidaten finden, dessen Quadrat höchstens x ist, und bist in etwa 31 Schritten fertig. Bei beiden Ansätzen lauert ein Überlauf: Das Quadrat eines Kandidaten passt nicht immer in 32 Bit.

Von null an hochzählen

Idee

Die Wurzel ist das größte r, für das r × r ≤ x gilt. Beginne bei r = 0, dessen Quadrat immer passt, und gehe weiter zu r + 1, solange das Quadrat der nächsten Zahl noch passt. Die Schleife endet beim ersten r, dessen Nachfolger zu groß ist – das ist genau die Wurzel. Für x = 17 passen die Quadrate 1, 4, 9 und 16, aber 25 nicht, also endet die Schleife bei 4.

Die Schleife wird einmal pro Einheit des Ergebnisses durchlaufen. Das größte Ergebnis ist hier 46340, also sind es höchstens 46340 Schritte, was schnell geht. Die Laufzeit beträgt allerdings O(√x) und wächst mit der Eingabe: Bei einem 64-Bit-x könnte die Berechnung etwa 3 × 10^9 Schritte erfordern.

Achte auf die letzte Prüfung. Für x = 2^31 - 1 quadriert die Schleife 46341, um festzustellen, dass die Zahl zu groß ist, und 46341 × 46341 = 2147488281 passt nicht in eine 32-Bit-Ganzzahl. Berechne das Quadrat mit 64 Bit.

Algorithmus

Setze root = 0.
Solange (root + 1) × (root + 1) ≤ x gilt, erhöhe root um 1.
Gib root zurück.

def mySqrt(x):
    root = 0
    while (root + 1) * (root + 1) <= x:
        root += 1
    return root

Binäre Suche nach der Antwort

Idee

Ordne die Kandidaten 0, 1, 2 bis x der Reihe nach an und stelle jedem dieselbe Frage: Ist sein Quadrat höchstens x? Die Antworten lauten ja, ja, ja und dann für jeden Kandidaten nach der Wurzel nein, denn die Quadrate werden nur größer. Die Wurzel ist das letzte Ja. Eine sortierte Folge von Ja, gefolgt von Nein, ist genau das, wofür die binäre Suche gedacht ist.

Behalte den Bereich lo bis hi der noch nicht entschiedenen Kandidaten bei, beginnend mit 0 bis x, und eine Variable best für das bisher größte Ja. Prüfe die Mitte mid. Wenn mid × mid ≤ x gilt, ist die Wurzel mid oder größer: Speichere den Wert in best und setze lo auf mid + 1. Andernfalls ist die Wurzel kleiner: Setze hi auf mid - 1. Wenn der Bereich leer ist, ist best die Wurzel.

Verfolge x = 17. Im Bereich von 0 bis 17 wird 8 geprüft (64, zu groß), dann im Bereich von 0 bis 7 die 3 (9, passt, best = 3), dann im Bereich von 4 bis 7 die 5 (25, zu groß), dann im Bereich von 4 bis 4 die 4 (16, passt, best = 4). Der Bereich ist leer und die Antwort lautet 4. Bei jedem Schritt halbiert sich der Bereich, also dauert es für x = 2^31 - 1 31 Schritte. Führe die Quadrierung mit 64 Bit aus: Das erste mid ist dort 1073741823.

Algorithmus

Setze lo = 0, hi = x und best = 0.
Berechne, solange lo ≤ hi gilt, mid, die Mitte des Bereichs.
Wenn mid × mid ≤ x (mit 64 Bit), setze best = mid und lo = mid + 1.
Andernfalls setze hi = mid - 1.
Gib best zurück.

def mySqrt(x):
    lo, hi = 0, x
    best = 0  # largest candidate seen so far whose square fits
    while lo <= hi:
        mid = (lo + hi) // 2
        if mid * mid <= x:
            best = mid  # mid fits, so try a larger root
            lo = mid + 1
        else:
            hi = mid - 1  # mid is too big
    return best

Stolperfallen und Grenzfälle

Die Suche selbst ist kurz; die Fehler stecken in der Arithmetik und den Grenzfällen.

Quadrieren mit 32 Bit. Für x = 2147483647 ist der erste mittlere Kandidat 1073741823, und sein Quadrat beträgt etwa 1.15 × 10^18. Bei einem 32-Bit-int läuft der Wert über und ergibt einen falschen Wert, der sogar klein genug erscheinen kann, um hineinzupassen. Führe die Multiplikation mit 64 Bit aus oder vergleiche stattdessen m ≤ x / m.
Quadrieren des nächsten Kandidaten mit 32 Bit in der Zählschleife. Die Wurzel von 2^31 - 1 ist 46340, und bei der letzten Prüfung der Schleife wird 46341 quadriert, was 2147488281 ergibt und damit über dem 32-Bit-Limit liegt.
Den Bereich über 32 Bit hinaus erweitern. Eine exklusive Grenze hi = x + 1 ist für das größte x gleich 2147483648 und damit eins über dem 32-Bit-Limit. Bei der inklusiven Grenze hi = x erreicht lo + hi im ersten Schritt genau 2147483647 und passt somit gerade noch hinein. Verwende 64-Bit-Indizes oder lo + (hi - lo) / 2.
Das zuletzt geprüfte mid zurückgeben, statt des letzten Werts, der noch passte. Für x = 17 endet die Suche nach dem Test von 5, was zu groß ist; die Antwort ist die gespeicherte 4.
Die kleinen Fälle kaputtmachen. Eine Suche, die bei lo = 1 beginnt, übersieht x = 0, und die Divisionsprüfung m ≤ x / m führt zu einer Division durch null, wenn m = 0. Prüfe 0 und 1 separat.

Häufige Fragen4

Wie berechnet man eine Quadratwurzel ohne eine eingebaute Funktion?

Für eine ganzzahlige Quadratwurzel führst du eine binäre Suche nach der Lösung durch. Die Kandidaten von 0 bis x teilen sich in eine Folge, deren Quadrate höchstens x sind, und eine Folge, deren Quadrate größer sind. Die binäre Suche findet den letzten Kandidaten der ersten Folge. Die andere verbreitete Methode ist das Newton-Verfahren: Es verbessert einen Schätzwert r mit (r + x / r) / 2, bis das Quadrat passt.

Wie hoch ist die Zeitkomplexität der binären Suche nach der Quadratwurzel?

O(log x) Zeit und O(1) Speicherplatz. In jedem Schritt wird der Bereich der möglichen Kandidaten halbiert, daher sind für x = 2^31 - 1 31 Schritte erforderlich. Von 0 an hochzuzählen dauert O(√x) Schritte, bei demselben x sind das 46340. Das ist hier in Ordnung, wächst bei 64-Bit-Eingaben aber schnell an.

Wie berechnet das Newton-Verfahren eine ganzzahlige Quadratwurzel?

Beginne mit r = x. Solange r × r > x gilt, ersetze r durch (r + x / r) / 2 mit ganzzahliger Division. Bei jedem Schritt wird r in Richtung der Wurzel verringert, ohne sie zu unterschreiten, und die Schleife endet beim ganzzahligen Anteil der Quadratwurzel. Für x = 2^31 - 1 sind 19 Schritte nötig, und die Anzahl der korrekten Stellen verdoppelt sich ungefähr mit jedem Schritt, sobald der Wert nahe genug liegt.

Warum benötigt die Lösung 64-Bit-Ganzzahlen, wenn die Antwort in 32 Bit passt?

Die Antwort ist höchstens 46340, aber die Kandidaten, die du testest, sind es nicht. Bei der binären Suche zwischen 0 und x wird zuerst ein Kandidat nahe 10^9 ausprobiert, und sein Quadrat liegt nahe 10^18 – weit über dem 32-Bit-Limit von etwa 2.1 × 10^9. Das Quadrieren mit 64 Bit hält den Vergleich exakt. Der Vergleich m ≤ x / m vermeidet das große Produkt vollständig.

Python

def mySqrt(x):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Eingabe

x = 17

Erwartet