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

Project Euler wird in den Tags erwähnt und viele der Probleme erfordern das Überprüfen von Zahlen >> 2^64. Die meisten der oben genannten Optimierungen funktionieren nicht so einfach, wenn man mit einem 80-Byte-Puffer arbeitet.

Ich habe java BigInteger und eine leicht modifizierte Version von Newtons Methode verwendet, eine, die besser mit ganzen Zahlen funktioniert. Das Problem war, dass exakte Quadrate n^2 statt zu n zu (n-1) konvergierten, weil n^2-1 = (n-1)(n+1) ist und der endgültige Fehler nur einen Schritt unter dem endgültigen Teiler lag und der Algorithmus terminierte. Es war einfach zu beheben, indem man dem ursprünglichen Argument vor der Berechnung des Fehlers eins hinzufügte. (Fügen Sie zwei für Kubikwurzeln usw. hinzu.)

Eine nette Eigenschaft dieses Algorithmus ist, dass man sofort erkennen kann, ob die Zahl ein perfektes Quadrat ist - der endgültige Fehler (nicht die Korrektur) in der Newtonschen Methode wird null sein. Eine einfache Modifikation ermöglicht es auch, floor(sqrt(x)) statt der nächstgelegenen Ganzzahl schnell zu berechnen. Das ist sehr nützlich bei mehreren Euler-Problemen.

Answer 2

Sie sollten den 2er-Potenzen-Teil von N von Anfang an loswerden.

2. Bearbeitung Der magische Ausdruck für m unten sollte sein

m = N - (N & (N-1));

und nicht wie geschrieben

Ende der 2. Bearbeitung

m = N & (N-1); // das niedrigste Bit von N
N /= m;
byte = N & 0x0F;
if ((m % 2) || (byte !=1 && byte !=9))
  return false;

1. Bearbeitung:

Kleine Verbesserung:

m = N & (N-1); // das niedrigste Bit von N
N /= m;
if ((m % 2) || (N & 0x07 != 1))
  return false;

Ende der 1. Bearbeitung

Fahren Sie nun wie gewohnt fort. Auf diese Weise haben Sie bis zum Gleitkomma-Teil bereits alle Zahlen eliminiert, bei denen der 2er-Potenzen-Teil ungerade ist (ungefähr die Hälfte), und dann betrachten Sie nur noch 1/8 von dem, was übrig bleibt. Das heißt, Sie führen den Gleitkomma-Teil für 6 % der Zahlen aus.

Answer 3

Der sqrt-Aufruf ist nicht perfekt genau, wie bereits erwähnt wurde, aber es ist interessant und lehrreich, dass er die anderen Antworten in Bezug auf Geschwindigkeit nicht übertrifft. Schließlich ist die Sequenz von Assembler-Anweisungen für eine Quadratwurzel winzig. Intel hat eine Hardwareanweisung, die von Java meiner Meinung nach nicht verwendet wird, weil sie nicht dem IEEE-Standard entspricht.

Warum ist es also langsam? Weil Java tatsächlich eine C-Routine über JNI aufruft, und es tatsächlich langsamer ist, dies zu tun, als eine Java-Unterprozedur aufzurufen, die selbst langsamer ist als die Inline-Ausführung. Das ist sehr ärgerlich, und Java hätte eine bessere Lösung finden sollen, beispielsweise das Einbinden von Gleitkommalibrary-Aufrufen, wenn nötig. Na ja.

In C++ vermute ich, dass alle komplexen Alternativen in Bezug auf Geschwindigkeit verlieren würden, aber ich habe sie nicht alle überprüft. Was ich gemacht habe, und was Java-Entwickler hilfreich finden dürften, ist ein einfacher Hack, eine Erweiterung des speziellen Falltests, der von A. Rex vorgeschlagen wurde. Verwenden Sie einen langen Wert als Bit-Array, der nicht auf Überschreitungen geprüft wird. Auf diese Weise haben Sie einen 64-Bit-Bool-Loopup.

typedef unsigned long long UVLONG
UVLONG pp1,pp2;

void init2() {
  for (int i = 0; i < 64; i++) {
    for (int j = 0; j < 64; j++)
      if (isPerfectSquare(i * 64 + j)) {
    pp1 |= (1 << j);
    pp2 |= (1 << i);
    break;
      }
   }
   cout << "pp1=" << pp1 << "," << pp2 << "\n";  
}

inline bool isPerfectSquare5(UVLONG x) {
  return pp1 & (1 << (x & 0x3F)) ? isPerfectSquare(x) : false;
}

Die Routine isPerfectSquare5 läuft auf meinem Core2-Duo-Rechner etwa 1/3 der Zeit. Ich vermute, dass weitere Anpassungen entlang der gleichen Linien die Zeit im Durchschnitt weiter reduzieren könnten, aber jedes Mal, wenn Sie überprüfen, tauschen Sie mehr Testen gegen mehr Eliminieren aus, so dass Sie nicht zu weit auf diesem Weg gehen können.

Sicherlich, anstatt einen separaten Test auf negativ zu haben, könnten Sie auf die gleiche Weise die oberen 6 Bits überprüfen.

Beachten Sie, dass ich nur mögliche Quadrate ausschließe, aber wenn ich einen potenziellen Fall habe, muss ich den ursprünglichen, inlinierten isPerfectSquare aufrufen.

Die init2-Routine wird einmal aufgerufen, um die statischen Werte von pp1 und pp2 zu initialisieren. Beachten Sie, dass ich in meiner Implementierung in C++ unsigned long long verwende, also müssten Sie, da Sie unterzeichnet sind, den >>>-Operator verwenden.

Es besteht kein inhärenter Bedarf für eine Grenzüberprüfung des Arrays, aber Javas Optimierer müssen diese Dinge ziemlich schnell herausfinden, also mache ich ihnen deswegen keinen Vorwurf.

Answer 4

Ich mag die Idee, eine fast korrekte Methode für einige der Eingaben zu verwenden. Hier ist eine Version mit einem höheren "Offset". Der Code scheint zu funktionieren und besteht meinen einfachen Testfall.

Ersetze einfach dein:

if(n < 410881L){...}

Code durch diesen:

if (n < 11043908100L) {
    //John Carmack Hack, konvertiert nach Java.
    // Siehe: http://www.codemaestro.com/reviews/9
    int i;
    float x2, y;

    x2 = n * 0.5F;
    y = n;
    i = Float.floatToRawIntBits(y);
    //Verwendung der magischen Zahl aus 
    //http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf
    //da diese genauer ist
    i = 0x5f375a86 - (i >> 1);
    y = Float.intBitsToFloat(i);
    y = y * (1.5F - (x2 * y * y));
    y = y * (1.5F - (x2 * y * y)); //Newton-Iteration, genauer

    sqrt = Math.round(1.0F / y);
} else {
    //Carmack Hack liefert eine falsche Antwort für n >= 11043908100.
    sqrt = (long) Math.sqrt(n);
}

Answer 5

Beim Betrachten der allgemeinen Bit-Länge (obwohl ich hier einen spezifischen Typ verwendet habe), habe ich versucht, den simplen Algorithmus wie folgt zu entwerfen. Es ist zunächst eine einfache und offensichtliche Überprüfung auf 0, 1, 2 oder <0 erforderlich. Der folgende Code ist einfach in dem Sinne, dass er keine vorhandenen mathematischen Funktionen verwendet. Die meisten Operatoren können durch bitweise Operatoren ersetzt werden. Ich habe jedoch keine Benchmarks getestet. Ich bin kein Experte in Mathematik oder Computeralgorithmusdesign, aber ich würde es begrüßen, wenn Sie auf Probleme hinweisen könnten. Ich weiß, dass es viele Verbesserungsmöglichkeiten gibt.

int main()
{
    unsigned int c1=0 ,c2 = 0;  
    unsigned int x = 0;  
    unsigned int p = 0;  
    int k1 = 0;  
    scanf("%d",&p);  
    if(p % 2 == 0) {  
        x = p/2; 
    }  
    else {  
        x = (p/2) +1;  
    }  
    while(x) 
    {
        if((x*x) > p) {  
            c1 = x;  
            x = x/2; 
        }else {  
            c2 = x;  
            break;  
        }  
    }  
    if((p%2) != 0)  
        c2++;

    while(c2 < c1) 
    {  
        if((c2 * c2 ) == p) {  
            k1 = 1;  
            break;  
        }  
        c2++; 
    }  
    if(k1)  
        printf("\n Perfektes Quadrat für %d", c2);  
    else  
        printf("\n Nicht perfekt, aber am nächsten dran an :%d :", c2);  
    return 0;  
}