Hallo Leute,
ich bin vorhin im Internet über den "fast inverse square root"-Algorithmus gestolpert. Da ich womöglich einen Nutzen dafür hätte wollte ich ihn dann erst mal auf Leistung testen.
Dazu habe ich eine Testmethode geschrieben, die zuerst ein Array mit einer anzahl n an zufälligen floats von 0 bis 10000 anlegt.
Danach lasse ich mir von jedem dieser Werte die inverse Quadratwurzel berechnen, und zwar im ersten Durchlauf einfach mit
und im zweiten mit dem invSqrt-Algorithmus (siehe unten).
Zwischen beiden Durchläufen habe ich mir jeweils die
geben lassen und habe dann im Nachhinein die Dauer beider durchläufe berechnet.
Das erstaunliche hierbei war, dass der "schnelle" Algorithmus auch bei wiederholtem Test bis zu vier mal so lang gebraucht hat.
Als ich dann die Methode dahingehend änderte, dass bei jedem Programmdurchlauf gleich hundert Testdurchläufe gemacht werden, stellte ich fest, dass bei einem Test mit n<1000 Werten pro Durchlauf immer so bei den ersten zwei oder drei tests die invSqrt methode langsamer ist und bei allen danach aber ca 5 mal so schnell! (bei kleineren n sind auch mehr langsame Durchläufe am Anfang.)
Kann mir das irgendwer erklären?! Ich dachte dass die JVM vielleicht noch irgendwas laden muss, aber wieso verlangsamt dass dann die einem Methode aber nicht die andere (oder zumindest unterschiedlich stark)?!
Hier ist nochmal der Algorithmus:
und hier mein ganzer code, falls ihr das auch mal testen wollt:
Ich werd den algorithmus auf jeden fall verwenden, aber interessieren tuts mich doch... =)
Grüße,
SuperSeppel13
ich bin vorhin im Internet über den "fast inverse square root"-Algorithmus gestolpert. Da ich womöglich einen Nutzen dafür hätte wollte ich ihn dann erst mal auf Leistung testen.
Dazu habe ich eine Testmethode geschrieben, die zuerst ein Array mit einer anzahl n an zufälligen floats von 0 bis 10000 anlegt.
Danach lasse ich mir von jedem dieser Werte die inverse Quadratwurzel berechnen, und zwar im ersten Durchlauf einfach mit
Code:
1f/(float)Math.sqrt(x)
Zwischen beiden Durchläufen habe ich mir jeweils die
Code:
System.nanoTime()
Das erstaunliche hierbei war, dass der "schnelle" Algorithmus auch bei wiederholtem Test bis zu vier mal so lang gebraucht hat.
Als ich dann die Methode dahingehend änderte, dass bei jedem Programmdurchlauf gleich hundert Testdurchläufe gemacht werden, stellte ich fest, dass bei einem Test mit n<1000 Werten pro Durchlauf immer so bei den ersten zwei oder drei tests die invSqrt methode langsamer ist und bei allen danach aber ca 5 mal so schnell! (bei kleineren n sind auch mehr langsame Durchläufe am Anfang.)
Kann mir das irgendwer erklären?! Ich dachte dass die JVM vielleicht noch irgendwas laden muss, aber wieso verlangsamt dass dann die einem Methode aber nicht die andere (oder zumindest unterschiedlich stark)?!
Hier ist nochmal der Algorithmus:
Java:
public static float invSqrt(float x){
float xhalf = 0.5f * x;
int i = Float.floatToRawIntBits(x); // store floating-point bits in integer
i = 0x5f3759df - (i >> 1); // initial guess for Newton's method
x = Float.intBitsToFloat(i); // convert new bits into float
x = x*(1.5f - xhalf*x*x); // One round of Newton's method
//x = x*(1.5f - xhalf*x*x); // optional second round, slower/more accurate
return x;
}
und hier mein ganzer code, falls ihr das auch mal testen wollt:
Java:
public class Test {
public static void main (String[] args){
int l = 100;
double sum = 0;
for(int i=0; i<100; i++){
sum += test();
}
System.out.println();
System.out.println("average: " + sum/l);//durchschnitt prozentuale zeitersparnis
}
static double test(){
final int l = 10000;//test-länge
float[] f = new float[l];
long start, half, end;
float sol;
for(int i = 1; i<l; i++){
f[i] = (float)Math.random()*10000f;//zufallszahlen generieren
}
start = System.nanoTime();
//durchlauf mit standart methode
for(int i=0; i<l; i++){
sol = 1f/(float)Math.sqrt(f[i]);
}
half = System.nanoTime();
//durchlauf mit invSqrt
for(int i=0; i<l; i++){
sol = invSqrt(f[i]);
}
end = System.nanoTime();
long t1 = half-start;//länge erster durchlauf
long t2 = end-half;//länge zweiter durchlauf
double d = (1d-(double)t2/t1)*100;//geschw.-zunahme in prozent
System.out.println(t1/1000000d);//in millisec
System.out.println(t2/1000000d);
System.out.println(d);
System.out.println();
return d;
}
public static float invSqrt(float x){
float xhalf = 0.5f * x;
int i = Float.floatToRawIntBits(x); // store floating-point bits in integer
i = 0x5f3759df - (i >> 1); // initial guess for Newton's method
x = Float.intBitsToFloat(i); // convert new bits into float
x = x*(1.5f - xhalf*x*x); // One round of Newton's method
//x = x*(1.5f - xhalf*x*x); // One round of Newton's method
return x;
}
}
Ich werd den algorithmus auf jeden fall verwenden, aber interessieren tuts mich doch... =)
Grüße,
SuperSeppel13