Quadratwurzelverfahren

Skym0sh0

Hallo leute

ich bin heute über ein Verfahren gestolpert was ich nicht ganz verstehe.

es geht um quadratwurzeln, bzw um eine verfahren sie zu errechnen(in der spiele programmierung)...

// wurzel.cpp
inline float FastWurzelExact(float r) //ist klar
{
unsigned long *ptr = NULL; //ein zeiger auf ein unsigned

if(r == 0.0f)
return 0.0f; //um unnötiges zu vermeiden
if(r < 0.0f)
r = -r;

float Value = r; //das ist ein startwert
float halfValue = 0.5f*r; //zweiter wert (wegen heron algorithmus)
ptr = (unsigned long*)&r; // was heisst das?
*ptr=(0xbe6f0000-*ptr)>>1; // und das?
float temp1Wurzel = r;
temp1Wurzel *= 1.5f-temp1Wurzel*temp1Wurzel*halfValue;
temp1Wurzel *= 1.5f-temp1Wurzel*temp1Wurzel*halfValue;
return Value*temp1Wurzel; //rest ist wieder klar
}

also das ist eine mischung aus dem heron algorithmus und einem trick auf die interne speicherung von gleitkommazahlen zuzugreifen

aber wie geht das? mit dieser hexzahl (ist übrigens 3194945536 im dezimal system)???
und was heisst (unsigned*)&r ???

mfg mosho

audacia

Zunächst zur binären Darstellung von Gleitkommazahlen:
http://de.wikipedia.org/wiki/Gleitkommazahl#IEEE_754_und_andere_Normen

Die Zeile

ptr = (unsigned long*)&r;

weist dem long-Zeiger die Adresse der Float-Zahl r zu; über den Zeiger kann man nun die Gleitkommazahl als Integerzahl behandeln.

Hier

*ptr=(0xbe6f0000-*ptr)>>1;

wird der als Integerzahl interpretierte Wert der Gleitkommazahl von 0xBE6F0000 abgezogen und um ein Bit nach rechts verschoben. Warum auch immer.

Wie das nun genau funktioniert, kannst du hier nachlesen.

Achja, und noch ein Tip: benutze am besten einfach std::sqrt() aus <cmath>. So etwas lohnt sich meist nicht, da viel zu plattformabhängig, fehleranfällig etc.

Skym0sh0

ja aber es ist viel schneller

und es geht um spiele programmieren...

naja danke ichw erd mir das mal angucken

drakon

Skym0sh0 schrieb:

ja aber es ist viel schneller

und es geht um spiele programmieren...

naja danke ichw erd mir das mal angucken

Glaubst du, dass die Typen, die diese Funktionen implementiet haben sich nix dabei geadacht haben?! Und das du das besser machen kannst, als ein erfahrener Programmierer?!

Und glaub mir.. In der Spieleprogrammierung hast du ganz andere Flaschenhälse, als ein paar sqrt ...

Skym0sh0

ach quatsch ich will nicht ein besseres verfahren schreiben sodnern das eifnach nur verstehen...

wobei ich hab den source code von quake 3
und da gibts auch so ein wurzelverfahren, aber das funktioniert nicht annähernd so gut wie das hier

(wurzel 9 -> quake: 0.345432)
(wurzel 9 -> das hier: 2.999999)

MFK

Skym0sh0 schrieb:

wobei ich hab den source code von quake 3
und da gibts auch so ein wurzelverfahren, aber das funktioniert nicht annähernd so gut wie das hier

Das funktioniert ganz gut, du hast bloß nicht verstanden, dass dabei gar nicht die Wurzel berechnet wird.

MFK schrieb:

Skym0sh0 schrieb:

wobei ich hab den source code von quake 3
und da gibts auch so ein wurzelverfahren, aber das funktioniert nicht annähernd so gut wie das hier

Das funktioniert ganz gut, du hast bloß nicht verstanden, dass dabei gar nicht die Wurzel berechnet wird.

Fast Inverse Squareroot.

Übrigens, ich hab das mal aus Interesse "gebencht". Mittlerweile ist der Geschwindigkeitsvorteil nicht mehr so nennenswert wie vielleicht zu Pentium MMX Zeiten (soll heißen, es lohnt sich nicht).

Skym0sh0

naja ich hab mir auch mal so einen benchmark geshcrieben

bis zu eienr millionen wurzeln pro sekudne ist alles ok

aber alles dadrüber braucht sqrt aus 'math.h' oder 'cmath' einige sekunden

10.000.000 wurzeln in knapp 20 oder 30 sekunden vom normalen sqrt errechnet

mit meinem vorgestellten geht das ganze in knapp 1 sekunde
und die näherung sit auch gut

wie gesagt wurzel 9 ist 2.99999...