En 2005 sort Quake 3 Arena, un jeu vidéo en 3D. Le moteur 3D de Quake est un des meilleurs et a été utilisé dans de nombreux autres jeux. On pourrait presque dire que Quake 3 Arena n'était pas vraiment un jeu mais plutôt une démonstration des capacités du moteur 3D.

Dans un moteur 3D, on modélise les objets à l'aide d'une grande quantité de triangle. Pour chaque triangle, il faut calculer l'incidence de la lumière. Cela nécessite de la géométrie. Il faut calculer les coordonnées du vecteur normal à la surface du triangle considéré et normaliser ce vecteur. Il faut alors beaucoup faire le calcul $\dfrac{1}{\sqrt{x}}$.

Calculer $\dfrac{1}{\sqrt{x}}$ n'est pas un problème si on doit le faire une fois. Mais si on doit le calculer chaque secondes des millions de fois, on va se rendre compte que le calcul prends trop de temps. En effet, le processeur dispose d'un circuit pour faire des multiplications et des additions / soustractions. Mais il n'a pas de circuit pour la racine et pas de circuit pour la division. Réaliser $\dfrac{1}{\sqrt{x}}$ nécessite alors de faire plusieurs calculs et cela prends du temps.

C'est là qu'intervient l'astuce utilisée dans le moteur 3D de Quake : En utilisant de façon inédite et astucieuse le codage des float, il est possible d'obtenir en quelques calculs, seulement des $\times$ et $-$, une excellent approximation de $\dfrac{1}{\sqrt{x}}$.

Remarque : Le calcul de Quake 3 était en float 32 bits. Mais comme nous avons étudié les float 64 bits, j'adapte un peu. Cela vous évitera d'avoir à vous adapter au cas 32 bits qui est semblable dans le principe.

ENTRÉE: float x
SORTIE: approximation de 1/sqrt(x)
DÉBUT
    dans le codage float 64 bits de x, décaler tous les bits de 1 case à droite
    y = le résultat obtenu, mais compris comme un entier 64 bits
    y = 6910482905085795328 - y
    z = les mêmes bits que y, mais compris comme un float
    RENVOYER z*(1.5-0.5*x*z*z)
FIN

Il faut donc :

• un décalage à droite des bits (très rapide)
• 2 soustraction (très rapide)
• 4 multiplications

Prenons le nombre $x = 25,5625$

1. Donnez le codage binaire de $x$ en utilisant le codage float 64 bits.
2. Décalez tous les bits de 1 case à droite.
3. Lisez ce codage binaire obtenu comme si c'était un entier ordinaire 64 bits. C'est $y$, donnez la valeur.
4. Faites le calcul $y = 6910482905085795328 - y$
5. Donnez le codage binaire du nombre obtenu en utilisant le codage d'un entier 64 bits.
6. Lisez ce codage binaire comme si c'était le codage d'un float 64 bits. Vous avez $z$, donnez sa valeur.
7. Faites le calcul $z\cdot (1,5-0,5\cdot x \cdot z \cdot z)$.

Le résultat final est censé être proche de $\dfrac{1}{\sqrt{x}}$. Vérifiez que c'est bien le cas.

Remarque : Lire un codage binaire comme ceci ou comme cela est fastidieux pour nous mais c'est instantané pour la machine. Les étapes qui prennent le plus de temps aux humains dans cet algorithme ont un coût nul pour la machine.

Référence : Vidéo en anglais