Les opérations bit à bit/Calculs flottants

Racine carrée inverse

Imprécision de la racine carré inverse.

Maintenant, nous allons voir une bidouille vraiment intéréssante, incorporée dans certains moteurs de jeux vidéo. On ne sait pas qui l'a inventé, mais il est devenu célèbre lors de la publication du code source de Quake 3 arena, un vieux fast FPS comme on en fait plus, très sympa à jouer en LAN. Un vrai jeu, quoi ! Bref, dans les jeux vidéo, on a souvent besoin de calculer $\frac{1}{\sqrt{x}}$. Ce calcul est évidemment effectué sur des nombres flottants. Mais à l'époque de la création de ce jeu vidéo, les opérations flottante étaient très lentes. Et elles le sont toujours un petit peu, d'ailleurs. Pour diminuer la lenteur du calcul de $\frac{1}{\sqrt{x}}$, on a inventé la Fast Inverse SQRT, afin de calculer celle-ci en utilisant uniquement des opérations entières ! Cet algorithme prend un flottant 32 bits, et donne une approximation de $\frac{1}{\sqrt{x}}$. La qualité de cette approximation est illustrée à droite. Cet algorithme est très simple, jugez plutôt :

float rsqrt(float x0)
{
    union {int ix; float x;};
    x = x0; // x can be viewed as int.
    float xhalf = 0.5f*x;
    ix = 0x5f375a82 - (ix >> 1); // Initial guess.
    x = x*(1.5f - xhalf*x*x); // Newton step.

    return x;
}