Comment calculer une racine carrée selon Carmack

John Carmack est un développeur de génie, et il est connu pour avoir développé le moteur de Wolfenstein 3D, Doom, Quake…

On imagine que pour avoir un temps de réponses assez rapide aux temps des 386, il fallait trouver des méthodes et algorithmes ingénieux.

Voici comment il calcule une racine inversée sans itération :

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;
}

source : Wikipedia

Laisser un commentaire