Wie kann man am schnellsten feststellen, ob die Quadratwurzel einer ganzen Zahl eine ganze Zahl ist?

Der schnellste Weg, um festzustellen, ob die Quadratwurzel einer ganzen Zahl eine ganze Zahl ist

Problembeschreibung

Ich suche das schnellster Weg Methode zur Bestimmung, ob eine lange ganze Zahl ein perfektes Quadrat ist (d. h. ihre Quadratwurzel ist eine andere ganze Zahl):

1. Ich habe es mit der integrierten Funktion Math.sqrt() gemacht, bin aber gespannt, ob es eine Möglichkeit gibt, das zu machen Verwendung von Ganzzahlfeldern, wodurch die Geschwindigkeit erhöht wird.


2. Es ist unpraktisch, eine Nachschlagetabelle zu verwalten (da es ungefähr 2^31,5 ganze Zahlen gibt, deren Quadrate kleiner als 2⁶³ sind).

Hier ist die ganz einfache und unkomplizierte Art, wie ich es jetzt mache:

{<br> if (n <pre class="brush:php;toolbar:false">return false;

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

_{Hinweis: Ich verwende diese Funktion in vielen Project Euler-Problemen. Daher wird dieser Code in Zukunft nicht mehr gewartet. Und diese Mikrooptimierung kann tatsächlich einen Unterschied machen, denn ein Teil der Herausforderung besteht darin, dass die Fertigstellung jedes Algorithmus weniger als eine Minute dauert, während diese Funktion bei manchen Problemen millionenfach aufgerufen werden muss.}

---

Ich habe verschiedene Lösungen für dieses Problem ausprobiert:

• Nach ausführlichen Tests habe ich festgestellt, dass das Hinzufügen von 0,5 zum Ergebnis von Math.sqrt() zumindest auf meinem Computer unnötig ist.


• Schnelle inverse Quadratwurzel ist schneller als Math.sqrt(), liefert aber falsche Ergebnisse für n >= 410881. Allerdings können wir, wie BobbyShaftoe vorgeschlagen hat, den FISR-Hack für n
  
• Newtons Methode ist viel langsamer als Math.sqrt(). Dies liegt wahrscheinlich daran, dass Math.sqrt() etwas Ähnliches wie Newtons Methode verwendet, jedoch in Hardware implementiert und daher viel schneller als in Java ist. Darüber hinaus erfordert die Newton-Methode immer noch die Verwendung von Gleitkommazahlen mit doppelter Genauigkeit.
positive 64-Bit-Ganzzahl mit Vorzeichen) und ist langsamer als Math.sqrt().

• Die binäre Suche ist noch langsamer. Dies ist sinnvoll, da eine binäre Suche durchschnittlich 16 Durchgänge erfordert, um die Quadratwurzel einer 64-Bit-Zahl zu finden.


• Laut Johns Tests ist die Verwendung einer or-Anweisung schneller als die Verwendung eines Schalters in C, aber in Java und C# scheint es keinen Unterschied zwischen einem or und einem Schalter zu geben.


• Ich habe auch versucht, eine Nachschlagetabelle zu erstellen (als privates statisches Array mit 64 booleschen Werten). Anstatt eine switch- oder or-Anweisung zu verwenden, würde ich dann einfach if(lookup[(int)(n&0x3F)]) { test } else return false; sagen. Zu meiner Überraschung ist dies (etwas) langsamer. Dies liegt daran, dass Array-Grenzen in Java überprüft werden.

Das obige ist der detaillierte Inhalt vonWie kann man am schnellsten feststellen, ob die Quadratwurzel einer ganzen Zahl eine ganze Zahl ist?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!