Schnellster Weg zu bestimmen, ob die Quadratwurzel einer ganzen Zahl eine ganze Zahl ist

Question

Ich suche nach dem schnellsten Weg, um festzustellen, ob ein long-Wert eine Quadratzahl ist (d. h., ob seine Quadratwurzel eine andere ganze Zahl ist):

1. Ich habe es auf einfache Weise gemacht, indem ich die integrierte Math.sqrt() Funktion verwendet habe, aber ich frage mich, ob es einen schnelleren Weg gibt, indem man sich auf den Bereich der Ganzzahlen beschränkt.
2. Das Führen einer Lookup-Tabelle ist unpraktisch (da es etwa 231,5 Ganzzahlen gibt, deren Quadrat kleiner als 263 ist).

Hier ist der sehr einfache und direkte Weg, den ich jetzt gehe:

public final static boolean isPerfectSquare(long n)
{
  if (n < 0)
    return false;

  long tst = (long)(Math.sqrt(n) + 0.5);
  return tst*tst == n;
}

_{Hinweis: Ich verwende diese Funktion in vielen <a href="http://projecteuler.net/" rel="noreferrer">Project Euler</a> Problemen. Also wird niemand anderer jemals diesen Code pflegen müssen. Und diese Art von Mikro-Optimierung könnte tatsächlich einen Unterschied machen, da ein Teil der Herausforderung darin besteht, jeden Algorithmus in weniger als einer Minute auszuführen, und diese Funktion in einigen Problemen Millionen von Malen aufgerufen werden muss.}

---

Ich habe die verschiedenen Lösungen für das Problem ausprobiert:

• Nach umfangreichen Tests habe ich festgestellt, dass das Hinzufügen von 0.5 zum Ergebnis von Math.sqrt() nicht notwendig ist, zumindest nicht auf meinem Computer.
• Der schnelle Kehrwert der Quadratwurzel war schneller, gab aber falsche Ergebnisse für n >= 410881. Jedoch, wie von BobbyShaftoe vorgeschlagen, können wir den FISR-Hack für n < 410881 verwenden.
• Newton's Methode war deutlich langsamer als Math.sqrt(). Das liegt wahrscheinlich daran, dass Math.sqrt() etwas Ähnliches wie Newton's Methode verwendet, aber in der Hardware implementiert ist, so dass sie viel schneller als in Java ist. Außerdem erforderte Newton's Methode immer noch die Verwendung von Doubles.
• Eine modifizierte Newton-Methode, die ein paar Tricks verwendete, so dass nur Ganzzahlenmathematik beteiligt war, erforderte einige Hacks, um Überlauf zu vermeiden (Ich möchte, dass diese Funktion mit allen positiven 64-Bit-Ganzzahlen funktioniert), und war immer noch langsamer als Math.sqrt().
• Die binäre Suche war noch langsamer. Das ergibt Sinn, da die binäre Suche im Durchschnitt 16 Durchläufe benötigen wird, um die Quadratwurzel einer 64-Bit-Zahl zu finden.
• Laut Johns Tests ist die Verwendung von or-Anweisungen in C++ schneller als die Verwendung eines switch, aber in Java und C# scheint es keinen Unterschied zwischen or und switch zu geben.
• Ich habe auch versucht, eine Lookup-Tabelle zu erstellen (als ein privates statisches Array von 64 booleschen Werten). Dann anstatt eines Switch- oder or-Statements würde ich einfach sagen if(lookup[(int)(n&0x3F)]) { test } else return false;. Zu meiner Überraschung war dies (nur leicht) langsamer. Das liegt daran, dass in Java Arraygrenzen überprüft werden.

Answer 1

Wenn Sie einen binären Schnitt durchführen, um die "richtige" Quadratwurzel zu finden, können Sie ziemlich leicht feststellen, ob der Wert, den Sie erhalten haben, nahe genug ist, um zu sagen:

(n+1)^2 = n^2 + 2n + 1
(n-1)^2 = n^2 - 2n + 1

Also, nachdem n^2 berechnet wurde, stehen die Optionen zur Verfügung:

• n^2 = Ziel: erledigt, true zurückgeben
• n^2 + 2n + 1 > Ziel > n^2: Sie sind nah dran, aber es ist nicht perfekt: false zurückgeben
• n^2 - 2n + 1 < Ziel < n^2: gleiches gilt
• Ziel < n^2 - 2n + 1: binärer Schnitt auf einem kleineren n
• Ziel > n^2 + 2n + 1: binärer Schnitt auf einem höheren n

(Entschuldigung, dies verwendet n als Ihre aktuelle Vermutung und Ziel für den Parameter. Entschuldigen Sie die Verwirrung!)

Ich weiß nicht, ob das schneller sein wird oder nicht, aber es ist einen Versuch wert.

EDIT: Der binäre Schnitt muss auch nicht den gesamten Bereich ganzer Zahlen umfassen (2^x)^2 = 2^(2x), daher können Sie, sobald Sie das höchste gesetzte Bit in Ihrem Ziel gefunden haben, (was mit einem Bit-Manipulations-Trick erreicht werden kann; ich weiß nicht mehr genau wie) schnell eine Reihe potenzieller Antworten erhalten. Aber eine naive binäre Suche dauert immer noch bis zu 31 oder 32 Durchläufe.

Answer 2

Ich habe meine eigene Analyse einiger der Algorithmen in diesem Thread durchgeführt und bin dabei zu einigen neuen Ergebnissen gekommen. Sie können diese alten Ergebnisse in der Bearbeitungshistorie dieser Antwort sehen, aber sie sind nicht korrekt, da ich einen Fehler gemacht und Zeit damit verschwendet habe, mehrere Algorithmen zu analysieren, die nicht annähernd gleich sind. Ich habe jedoch die Lehren aus verschiedenen Antworten gezogen und habe jetzt zwei Algorithmen, die den "Gewinner" dieses Threads vernichten. Hier ist der Kernpunkt, den ich anders mache als alle anderen:

// This is faster because a number is divisible by 2^4 or more only 6% of the time
// and more than that a vanishingly small percentage.
while((x & 0x3) == 0) x >>= 2;
// This is effectively the same as the switch-case statement used in the original
// answer. 
if((x & 0x7) != 1) return false;

Diese einfache Zeile, die in den meisten Fällen eine oder zwei sehr schnelle Anweisungen hinzufügt, vereinfacht jedoch die switch-case Anweisung zu einer if-Anweisung zusammenfassen. Dies kann jedoch die Laufzeit verlängern, wenn viele der getesteten Zahlen signifikante Zweierpotenzen haben.

Die folgenden Algorithmen sind wie folgt:

• Internet - Kip's gepostete Antwort
• Durron - Meine modifizierte Antwort auf der Grundlage der Antwort in einem Durchgang
• DurronTwo - Meine modifizierte Antwort unter Verwendung der Two-Pass-Antwort (von @JohnnyHeggheim), mit einigen anderen leichten Änderungen.

Hier ist ein Beispiel für die Laufzeit, wenn die Zahlen mit Math.abs(java.util.Random.nextLong())

 0% Scenario{vm=java, trial=0, benchmark=Internet} 39673.40 ns; ?=378.78 ns @ 3 trials
33% Scenario{vm=java, trial=0, benchmark=Durron} 37785.75 ns; ?=478.86 ns @ 10 trials
67% Scenario{vm=java, trial=0, benchmark=DurronTwo} 35978.10 ns; ?=734.10 ns @ 10 trials

benchmark   us linear runtime
 Internet 39.7 ==============================
   Durron 37.8 ============================
DurronTwo 36.0 ===========================

vm: java
trial: 0

Und hier ist ein Beispiel für die Laufzeit, wenn es nur für die erste Million Longs ausgeführt wird:

 0% Scenario{vm=java, trial=0, benchmark=Internet} 2933380.84 ns; ?=56939.84 ns @ 10 trials
33% Scenario{vm=java, trial=0, benchmark=Durron} 2243266.81 ns; ?=50537.62 ns @ 10 trials
67% Scenario{vm=java, trial=0, benchmark=DurronTwo} 3159227.68 ns; ?=10766.22 ns @ 3 trials

benchmark   ms linear runtime
 Internet 2.93 ===========================
   Durron 2.24 =====================
DurronTwo 3.16 ==============================

vm: java
trial: 0

Wie Sie sehen können, DurronTwo schneidet bei großen Eingaben besser ab, weil er den Zaubertrick sehr oft anwenden kann, wird aber im Vergleich zum ersten Algorithmus und Math.sqrt weil die Zahlen so viel kleiner sind. Inzwischen ist die einfachere Durron ist ein riesiger Gewinner, weil er in der ersten Million Zahlen nicht viele Male durch 4 teilen muss.

Hier ist Durron :

public final static boolean isPerfectSquareDurron(long n) {
    if(n < 0) return false;
    if(n == 0) return true;

    long x = n;
    // This is faster because a number is divisible by 16 only 6% of the time
    // and more than that a vanishingly small percentage.
    while((x & 0x3) == 0) x >>= 2;
    // This is effectively the same as the switch-case statement used in the original
    // answer. 
    if((x & 0x7) == 1) {

        long sqrt;
        if(x < 410881L)
        {
            int i;
            float x2, y;

            x2 = x * 0.5F;
            y  = x;
            i  = Float.floatToRawIntBits(y);
            i  = 0x5f3759df - ( i >> 1 );
            y  = Float.intBitsToFloat(i);
            y  = y * ( 1.5F - ( x2 * y * y ) );

            sqrt = (long)(1.0F/y);
        } else {
            sqrt = (long) Math.sqrt(x);
        }
        return sqrt*sqrt == x;
    }
    return false;
}

Und DurronTwo

public final static boolean isPerfectSquareDurronTwo(long n) {
    if(n < 0) return false;
    // Needed to prevent infinite loop
    if(n == 0) return true;

    long x = n;
    while((x & 0x3) == 0) x >>= 2;
    if((x & 0x7) == 1) {
        long sqrt;
        if (x < 41529141369L) {
            int i;
            float x2, y;

            x2 = x * 0.5F;
            y = x;
            i = Float.floatToRawIntBits(y);
            //using the magic number from 
            //http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf
            //since it more accurate
            i = 0x5f375a86 - (i >> 1);
            y = Float.intBitsToFloat(i);
            y = y * (1.5F - (x2 * y * y));
            y = y * (1.5F - (x2 * y * y)); //Newton iteration, more accurate
            sqrt = (long) ((1.0F/y) + 0.2);
        } else {
            //Carmack hack gives incorrect answer for n >= 41529141369.
            sqrt = (long) Math.sqrt(x);
        }
        return sqrt*sqrt == x;
    }
    return false;
}

Und mein Benchmark-Kabelbaum: (Benötigt Google caliper 0.1-rc5)

public class SquareRootBenchmark {
    public static class Benchmark1 extends SimpleBenchmark {
        private static final int ARRAY_SIZE = 10000;
        long[] trials = new long[ARRAY_SIZE];

        @Override
        protected void setUp() throws Exception {
            Random r = new Random();
            for (int i = 0; i < ARRAY_SIZE; i++) {
                trials[i] = Math.abs(r.nextLong());
            }
        }

        public int timeInternet(int reps) {
            int trues = 0;
            for(int i = 0; i < reps; i++) {
                for(int j = 0; j < ARRAY_SIZE; j++) {
                    if(SquareRootAlgs.isPerfectSquareInternet(trials[j])) trues++;
                }
            }

            return trues;   
        }

        public int timeDurron(int reps) {
            int trues = 0;
            for(int i = 0; i < reps; i++) {
                for(int j = 0; j < ARRAY_SIZE; j++) {
                    if(SquareRootAlgs.isPerfectSquareDurron(trials[j])) trues++;
                }
            }

            return trues;   
        }

        public int timeDurronTwo(int reps) {
            int trues = 0;
            for(int i = 0; i < reps; i++) {
                for(int j = 0; j < ARRAY_SIZE; j++) {
                    if(SquareRootAlgs.isPerfectSquareDurronTwo(trials[j])) trues++;
                }
            }

            return trues;   
        }
    }

    public static void main(String... args) {
        Runner.main(Benchmark1.class, args);
    }
}

UPDATE: Ich habe einen neuen Algorithmus entwickelt, der in einigen Szenarien schneller und in anderen langsamer ist, und ich habe verschiedene Benchmarks auf der Grundlage verschiedener Eingaben erhalten. Wenn wir modulo berechnen 0xFFFFFF = 3 x 3 x 5 x 7 x 13 x 17 x 241 können wir 97,82 % der Zahlen eliminieren, die keine Quadrate sein können. Dies lässt sich (quasi) in einer Zeile mit 5 bitweisen Operationen bewerkstelligen:

if (!goodLookupSquares[(int) ((n & 0xFFFFFFl) + ((n >> 24) & 0xFFFFFFl) + (n >> 48))]) return false;

Der resultierende Index ist entweder 1) der Rückstand, 2) der Rückstand + 0xFFFFFF oder 3) der Rückstand + 0x1FFFFFE . Natürlich brauchen wir eine Nachschlagetabelle für Reste modulo 0xFFFFFF die etwa 3 MB groß ist (in diesem Fall als ascii-Text-Dezimalzahlen gespeichert, nicht optimal, aber mit einem entsprechenden Programm deutlich verbesserungsfähig). ByteBuffer und so weiter. Aber da es sich um eine Vorberechnung handelt, ist das nicht so wichtig. Sie können die Datei hier finden (oder erstellen Sie sie selbst):

public final static boolean isPerfectSquareDurronThree(long n) {
    if(n < 0) return false;
    if(n == 0) return true;

    long x = n;
    while((x & 0x3) == 0) x >>= 2;
    if((x & 0x7) == 1) {
        if (!goodLookupSquares[(int) ((n & 0xFFFFFFl) + ((n >> 24) & 0xFFFFFFl) + (n >> 48))]) return false;
        long sqrt;
        if(x < 410881L)
        {
            int i;
            float x2, y;

            x2 = x * 0.5F;
            y  = x;
            i  = Float.floatToRawIntBits(y);
            i  = 0x5f3759df - ( i >> 1 );
            y  = Float.intBitsToFloat(i);
            y  = y * ( 1.5F - ( x2 * y * y ) );

            sqrt = (long)(1.0F/y);
        } else {
            sqrt = (long) Math.sqrt(x);
        }
        return sqrt*sqrt == x;
    }
    return false;
}

Ich lade sie in eine boolean Array wie dieses:

private static boolean[] goodLookupSquares = null;

public static void initGoodLookupSquares() throws Exception {
    Scanner s = new Scanner(new File("24residues_squares.txt"));

    goodLookupSquares = new boolean[0x1FFFFFE];

    while(s.hasNextLine()) {
        int residue = Integer.valueOf(s.nextLine());
        goodLookupSquares[residue] = true;
        goodLookupSquares[residue + 0xFFFFFF] = true;
        goodLookupSquares[residue + 0x1FFFFFE] = true;
    }

    s.close();
}

Beispiel-Laufzeit. Es schlägt Durron (Version eins) in jedem Versuch, den ich durchgeführt habe.

 0% Scenario{vm=java, trial=0, benchmark=Internet} 40665.77 ns; ?=566.71 ns @ 10 trials
33% Scenario{vm=java, trial=0, benchmark=Durron} 38397.60 ns; ?=784.30 ns @ 10 trials
67% Scenario{vm=java, trial=0, benchmark=DurronThree} 36171.46 ns; ?=693.02 ns @ 10 trials

  benchmark   us linear runtime
   Internet 40.7 ==============================
     Durron 38.4 ============================
DurronThree 36.2 ==========================

vm: java
trial: 0

Answer 3

Es sollte viel schneller sein, das Newton-Verfahren zu verwenden, um die ganzzahlige Quadratwurzel zu berechnen, und dann diese Zahl zu quadrieren und zu überprüfen, wie Sie es in Ihrer aktuellen Lösung tun. Das Newton-Verfahren ist die Grundlage für die Carmack-Lösung, die in einigen anderen Antworten erwähnt wird. Sie sollten eine schnellere Antwort bekommen können, da Sie nur am ganzzahligen Teil der Wurzel interessiert sind und den Approximationsalgorithmus früher anhalten können.

Ein weiterer Optimierungsvorschlag: Wenn die digitale Wurzel einer Zahl nicht auf 1, 4, 7 oder 9 endet, ist die Zahl nicht eine perfekte Quadratzahl. Dies kann als schneller Weg verwendet werden, um 60% Ihrer Eingaben zu eliminieren, bevor der langsamere Quadratwurzelalgorithmus angewendet wird.

Answer 4

Ich möchte, dass diese Funktion mit allen positiven 64-Bit-ganzen Zahlen funktioniert

Math.sqrt() funktioniert mit Dezimalzahlen als Eingabeparametern, also erhalten Sie keine genauen Ergebnisse für Zahlen größer als 2^53.

Answer 5

Ein Integer-Problem verdient eine Integer-Lösung. Folglich

Führen Sie eine binäre Suche auf den (nicht-negativen) ganzen Zahlen durch, um die größte ganze Zahl t zu finden, sodass t**2 <= n. Überprüfen Sie dann, ob r**2 = n genau ist. Dies dauert O(log n) Zeit.

Wenn Sie nicht wissen, wie Sie eine binäre Suche auf den positiven ganzen Zahlen durchführen können, weil die Menge unbeschränkt ist, ist es einfach. Beginnen Sie damit, Ihre steigende Funktion f (oben f(t) = t**2 - n) auf Potenzen von zwei zu berechnen. Wenn Sie sehen, dass sie positiv wird, haben Sie eine obere Grenze gefunden. Dann können Sie eine Standard-Binärsuche durchführen.