Ich suche nach dem schnellsten Weg, um festzustellen, ob ein "langer" Wert ein perfektes Quadrat ist (d.h. seine Quadratwurzel ist eine andere ganze Zahl):
Math.sqrt()
Funktion, aber ich frage mich, ob es einen Weg gibt, es schneller zu machen, indem man
indem man sich auf den Integer-Bereich beschränkt.Hier ist die sehr einfache und geradlinige Art und Weise, wie ich es jetzt mache:
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 Projekt Euler Problemen. So muss niemand sonst diesen Code pflegen. 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 dieses Problem ausprobiert:
0,5
zum Ergebnis von Math.sqrt() nicht notwendig ist, zumindest nicht auf meinem Rechner.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 ist als in Java. Außerdem erforderte die Newton-Methode immer noch die Verwendung von Doubles.Math.sqrt()
.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.or
-Anweisung einfach sagen: if(lookup[(int)(n&0x3F)]) { test } else return false;
. Zu meiner Überraschung war dies (nur geringfügig) langsamer. Das liegt daran, dass Array-Grenzen in Java geprüft werden.Ich habe über die schrecklichen Zeiten nachgedacht, die ich im Kurs Numerische Analyse verbracht habe.
Und dann erinnerte ich mich, dass da diese Funktion aus dem Quake-Quellcode im Netz kursierte:
float Q_rsqrt( float number )
{
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = * ( long * ) &y; // evil floating point bit level hacking
i = 0x5f3759df - ( i >> 1 ); // wtf?
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
// y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed
#ifndef Q3_VM
#ifdef __linux__
assert( !isnan(y) ); // bk010122 - FPE?
#endif
#endif
return y;
}
Die im Grunde eine Quadratwurzel berechnet, unter Verwendung der Newtonschen Näherungsfunktion (kann mich nicht mehr an den genauen Namen erinnern).
Es sollte brauchbar sein und könnte sogar schneller sein, es ist von einem der phänomenalen id Software Spiel!
Es ist in C++ geschrieben, aber es sollte nicht zu schwer sein, die gleiche Technik in Java wiederzuverwenden, sobald Sie die Idee bekommen:
Ich habe es ursprünglich gefunden unter: http://www.codemaestro.com/reviews/9.
Newtons Methode erklärt bei wikipedia: http://en.wikipedia.org/wiki/Newton%27s_method
Sie können dem Link folgen, um mehr über die Funktionsweise zu erfahren, aber wenn Sie sich nicht dafür interessieren, dann ist das ungefähr das, woran ich mich erinnere, wenn ich den Blog lese und den Kurs "Numerische Analysis" belege:
* (long*) &y
ist im Grunde eine schnelle Konvertierung in eine lange Funktion, so dass ganzzahlige Operationen auf die rohen Bytes angewendet werden können.0x5f3759df - (i >> 1);
ist ein vorberechneter Startwert für die Approximationsfunktion.Die Approximationsfunktion liefert umso genauere Werte, je öfter man die Funktion über das Ergebnis iteriert. Im Fall von Quake ist eine Iteration "gut genug", aber wenn das für Sie nicht zutrifft, können Sie so viele Iterationen hinzufügen, wie Sie brauchen.
Dies sollte schneller sein, weil es die Anzahl der Divisionsoperationen, die bei der naiven quadratischen Verwurzelung durchgeführt werden, auf eine einfache Division durch 2 (eigentlich eine * 0.5F
Multiplikationsoperation) reduziert und sie stattdessen durch eine feste Anzahl von Multiplikationsoperationen ersetzt.
Wenn Sie mit einem binären Chop versuchen, die "richtige" Quadratwurzel zu finden, können Sie relativ leicht feststellen, ob der Wert nahe genug ist, um ihn zu erkennen:
(n+1)^2 = n^2 + 2n + 1
(n-1)^2 = n^2 - 2n + 1
Nachdem man also n^2
berechnet hat, gibt es folgende Möglichkeiten:
n^2 = Ziel
: fertig, Rückgabe truen^2 + 2n + 1 > target > n^2
: du bist nahe dran, aber es ist nicht perfekt: return falsen^2 - 2n + 1 < Ziel < n^2
: ditoZiel < n^2 - 2n + 1
: Binäres Chop auf ein kleineres n
Ziel > n^2 + 2n + 1
: Binäre Zerlegung auf ein höheres n
(Entschuldigung, hier wird n
als aktuelle Schätzung und target
als Parameter verwendet. Ich entschuldige mich für die Verwirrung!)
Ich weiß nicht, ob dies schneller ist oder nicht, aber es ist einen Versuch wert.
EDIT: Die binäre Zerlegung muss nicht den gesamten Bereich der ganzen Zahlen berücksichtigen, auch nicht (2^x)^2 = 2^(2x)
, so dass man, sobald man das oberste Bit im Ziel gefunden hat (was man mit einem Bit-Twiddling-Trick machen kann; ich habe vergessen, wie genau), schnell eine Reihe von möglichen Antworten erhalten kann. Wohlgemerkt, ein naives binäres Hacken dauert immer noch nur bis zu 31 oder 32 Iterationen.
Wenn Sie Geschwindigkeit wollen, da Ihre ganzen Zahlen von endlicher Größe sind, vermute ich, dass der schnellste Weg beinhalten würde (a) Partitionierung der Parameter nach Größe (z. B. in Kategorien von größten Bit gesetzt), dann überprüfen Sie den Wert gegen ein Array von perfekten Quadraten innerhalb dieses Bereichs.