Wie man überprüft, ob die Quadratwurzel einer Zahl eine ganze Zahl ist: 5 Methoden in Java

Einleitung: Eine Aufgabe, die Stack Overflow sprengt

Stellen Sie sich vor: Sie schreiben Code, der Tausende von Zahlen pro Sekunde verarbeitet. Sie müssen diejenigen herausfiltern, deren Quadratwurzel eine ganze Zahl ist (1, 4, 9, 16…). Was könnte da schon schwierig sein? Sie nehmen Math.sqrt(), prüfen den Rest – und fertig. Aber so einfach ist es nicht.

Die Frage „Fastest way to determine if an integer's square root is an integer“ auf Stack Overflow hat bereits über 100.000 Aufrufe. Warum? Weil Math.sqrt() eine Gleitkommaoperation ist, die langsam und anfällig für Rundungsfehler ist. Bei großen Zahlen (z. B. 2^50) kann double einfach „lügen“.

In diesem Artikel analysieren wir 5 Ansätze in Java: vom naivsten bis zu schnellen Algorithmen, die Bitoperationen und Ganzzahlarithmetik nutzen. Sie erfahren, welche Methode wirklich schneller und welche sicherer ist. Los geht's!

Problemstellung

Wir müssen eine Methode boolean isPerfectSquare(long n) schreiben, die true zurückgibt, wenn n ein perfektes Quadrat (perfect square) ist. Beispiele:

\n
• isPerfectSquare(25) → true (5*5)
\n
• isPerfectSquare(26) → false
\n
• isPerfectSquare(0) → true (0*0)
\n
• isPerfectSquare(1) → true
\n

Wir testen mit long, da int ein Spezialfall ist und long mehr Raum für Fehler bietet.

Methode 1: Naiv – Math.sqrt + Restprüfung

Der einfachste Weg, der einem Anfänger in den Sinn kommt:

public static boolean isPerfectSquareSqrt(long n) {\n    if (n < 0) return false;\n    double sqrt = Math.sqrt(n);\n    long floorSqrt = (long) sqrt;\n    return floorSqrt * floorSqrt == n;\n}\n

Problem Nr. 1: Genauigkeit. Für Zahlen größer als ~2^53 (9.007.199.254.740.991) kann double ganze Zahlen nicht mehr genau darstellen. Beispiel: n = 999999999999999999L – Math.sqrt liefert ein falsches Ergebnis.

Problem Nr. 2: Geschwindigkeit. Math.sqrt ist eine CPU-Instruktion (FSQRT), aber dennoch langsamer als einfache arithmetische Operationen.

Wann verwenden: Nur für int oder kleine long (< 10^12), wenn Geschwindigkeit nicht kritisch ist.

Methode 2: Ganzzahlige Quadratwurzel mit Newton-Raphson

Das Newton-Verfahren (Newton-Raphson) ist eine klassische Methode, um die Quadratwurzel ohne Gleitkommazahlen zu berechnen. Die Näherung wird iterativ verbessert:

public static boolean isPerfectSquareNewton(long n) {\n    if (n < 0) return false;\n    if (n < 2) return true;\n    long x = n;\n    long y = (x + 1) / 2;\n    while (y < x) {\n        x = y;\n        y = (y + n / y) / 2;\n    }\n    return x * x == n;\n}\n

Der Algorithmus konvergiert sehr schnell – in O(log log n) Iterationen. Für Zahlen bis Long.MAX_VALUE werden nur 6-8 Iterationen benötigt.

Vorteile: Absolute Genauigkeit für alle long (bis 2^63-1). Verwendet kein double.

Nachteile: Division ist eine teure Operation. Für sehr kleine Zahlen (n < 4) kann eine Prüfung am Anfang hinzugefügt werden.

Methode 3: Binäre Suche der Wurzel

Ein weiterer klassischer Algorithmus – wir suchen die Wurzel mit binärer Suche im Intervall [0, n]. Für long beträgt der maximale Wurzelwert 3.037.000.499 (sqrt(Long.MAX_VALUE)).

public static boolean isPerfectSquareBinary(long n) {\n    if (n < 0) return false;\n    if (n < 2) return true;\n    long low = 1;\n    long high = 3037000499L; // sqrt(Long.MAX_VALUE)\n    while (low <= high) {\n        long mid = (low + high) >>> 1;\n        long square = mid * mid;\n        if (square == n) return true;\n        else if (square < n) low = mid + 1;\n        e