Racine Carré

Publié le par Chkone

En C++ pour faire une racine carré en général on utilise la fonction de la bibliothèque standart sqrt et bien pas John Carmack developpeur pour Wolfenstein 3D, Doom et Quake. Et bien lui il est bizarre regarder comment il fait :
 float SquareRootFloat(float number)
{
float x, y; const float f = 1.5F;
x = number * 0.5F;
y = number;
long i;
i = * ( long * ) &y;
i = 0x5f3759df - ( i >> 1 );
y = * ( float * ) &i;
y = y * ( f - ( x * y * y ) );
//y = y * ( f - ( x * y * y ) );
return number * y;
}

Franchement j'ai pas vraiment compris comment il fait ce bougre de Carmack est vraiment bizarre... Il passe des float en long. Cette ligne est vraiment bizarre :  "i = * ( long * ) &y;" ou encore "i = 0x5f3759df - ( i >> 1 );" Mais qu'est ce qui lui a pris de décoler des bits comme ça... Il parait que le mystère de la fonction ce trouve dans le nombre magique (en hexa biensur) : 0x5f3759df.

Mais ce petit John ne s'arrête pas là il nous fait la fonction racine inverse :
 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 ); // what the fuck?
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; }
Bizarre comme mec ce John en plus ces fonctions sont de bonnes aproximation :S Mais un mathématicien s'est penché sur la fonction racine inverse et en à fait une plus rapide :
 float InvSqrt(float x)
{
float xhalf = 0.5f*x;
int i = *(int*)&x; // get bits for floating value
i = 0x5f375a86- (i>>1); // gives initial guess y0
x = *(float*)&i; // convert bits back to float
x = x*(1.5f-xhalf*x*x); // Newton step, repeating increases accuracy
return x;
}
Celle là c'est du Chris Lomont. Si ça vous tente de comprendre comment ça marche le matheux à publier un petit pdf : ici

Bon le monde de la programmation est vraiment bizarre...

Publié dans C++

Commenter cet article

nicolas66 18/06/2008 00:45

Remarques :

* Les fonctions de John Carmack sont sous licence GPL
* La fonction de Chris Lomont est sous Copyright