Comprendre la Racine Carrée Inverse Rapide de Quake
Un article et un article de recherche décrivent un moyen rapide et apparemment magique de calculer la racine carrée inverse ($1/\sqrt{x}$), utilisé dans le jeu Quake.
Je ne suis pas un expert en graphisme, mais j’apprécie pourquoi les racines carrées sont utiles. Le théorème de Pythagore calcule la distance entre les points, et la division par la distance aide à normaliser les vecteurs. (La normalisation n’est souvent qu’un terme de fantaisie pour la division.)
Des jeux 3D comme Quake divisent par des zillions de distance (oui zillions) de fois par seconde, donc des améliorations de performances « mineures » aident énormément. Nous ne voulons pas prendre la racine carrée et diviser de manière régulière: l’exponentiation et la division sont vraiment, vraiment chères pour le CPU.
Compte tenu de ces conditions, voici la formule magique pour obtenir11 / \sqrt {x}$, telle que trouvée dans Quake (mes commentaires insérés):
Ma compréhension: Cet incroyable hack estime la racine inverse en utilisant la méthode d’approximation de Newton, et commence par une excellente supposition initiale.
Pour faire la supposition, il faut un nombre à virgule flottante en notation scientifique et annule & la moitié de l’exposant pour obtenir quelque chose proche de la racine carrée inverse. Il exécute ensuite une ronde de la méthode d’approximation de Newton pour affiner davantage l’estimation et tada, nous avons quelque chose près de la racine carrée inverse.
Méthode d’approximation de Newton
La méthode de Newton peut être utilisée pour trouver des racines approximatives de n’importe quelle fonction. Vous pouvez continuer à itérer la méthode pour vous rapprocher de plus en plus de la racine, mais cette fonction n’utilise qu’une étape! Voici un cours intensif sur la méthode de Newton (c’était nouveau pour moi):
Vous pouvez continuer à répéter ce processus (en branchant votre nouvelle estimation dans la formule) et obtenir des approximations plus proches pour votre racine. Finalement, vous avez une « nouvelle supposition » qui rend f (nouvelle supposition) vraiment, vraiment proche de zéro — c’est une racine! (Ou assez proche pour le travail du gouvernement, comme on dit).
De toute évidence, nous voulons réduire notre erreur le plus possible. Cela signifie trouver le « x » qui fait error (x) = 0, ce qui revient à trouver la racine de l’équation d’erreur. Si l’on branche l’erreur (x) dans la formule d’approximation de Newton:
et prenez les dérivés appropriés:
nous pouvons les brancher pour obtenir la formule pour une meilleure estimation:
C’est exactement l’équation que vous voyez dans le code ci-dessus, en vous rappelant que x est notre nouvelle supposition (g) et que « xhalf » est la moitié de la valeur d’origine (0,5 i i$):
x = x*(1.5f - xhalf*x*x);
Avec cette formule, nous pouvons commencer par une supposition « g » et répéter la formule pour obtenir de meilleures suppositions. Essayez cette démo pour utiliser plusieurs itérations pour trouver le carré inverse:
Alors mes amis, la question devient: « Comment pouvons-nous faire une bonne supposition initiale? »
Faire une bonne estimation
Qu’est-ce qu’une bonne estimation pour la racine carrée inverse? C’est un peu une question piège our notre meilleure supposition pour la racine carrée inverse est la racine carrée inverse elle-même!
Ok hotshot, vous demandez, comment obtenons-nous réellement11 /\sqrt{x}??
C’est là que la magie entre en jeu. Disons que vous avez un nombre sous forme d’exposant ou de notation scientifique:
Maintenant, si vous voulez trouver la racine carrée régulière, vous divisez simplement l’exposant par 2:
Et si vous voulez la racine carrée inverse, divisez l’exposant par -2 pour inverser le signe:
Alors, comment pouvons-nous obtenir l’exposant d’un nombre sans autres opérations coûteuses?
Les flotteurs sont stockés sous la forme d’exposant de mantisse
Eh bien, nous avons de la chance. Les nombres à virgule flottante sont stockés par les ordinateurs sous forme d’exposant de mantisse, il est donc possible d’extraire et de diviser l’exposant!
Mais au lieu de faire explicitement la division (coûteuse pour le CPU), le code utilise un autre hack intelligent: il décale des bits. Le décalage vers la droite d’une position revient à diviser par deux (vous pouvez essayer cela pour n’importe quelle puissance de 2, mais cela tronquera le reste). Et si vous voulez obtenir un nombre négatif, au lieu de multiplier par -1 (les multiplications sont chères), soustrayez simplement le nombre de « 0 » (les soustractions sont bon marché).
Ainsi, le code convertit le nombre à virgule flottante en un entier. Il décale ensuite les bits d’un, ce qui signifie que les bits d’exposant sont divisés par 2 (lorsque nous transformons finalement les bits en un flotteur). Et enfin, pour nier l’exposant, nous soustrayons du nombre magique 0x5f3759df. Cela fait quelques choses: il préserve la mantisse (la partie non exponentielle, alias 5 in: $5 \ cdot 10 ^ 6^), gère les exposants pairs impairs, déplace les bits de l’exposant dans la mantisse, et toutes sortes de trucs géniaux. Le papier a plus de détails et d’explications, je n’ai pas tout compris la première fois. Comme toujours, n’hésitez pas à commenter si vous avez une meilleure explication de ce qui se passe.
Le résultat est que nous obtenons une supposition initiale qui est vraiment proche de la racine carrée inverse réelle! Nous pouvons ensuite faire un seul tour de la méthode de Newton pour affiner la conjecture. Plus de tours sont possibles (à des frais de calcul supplémentaires), mais un tour est tout ce dont vous avez besoin pour la précision requise.
Alors, pourquoi le nombre magique?
Le grand hack est la façon dont les entiers et les nombres à virgule flottante sont stockés. Des nombres à virgule flottante comme55.4\cdot 10^6 store stockent leur exposant dans une plage de bits distincte de « 5.4 ». Lorsque vous déplacez le nombre entier, vous divisez l’exposant par 2, ainsi que le nombre (5.4) par 2 également. C’est là que le nombre magique entre en jeu it il fait des corrections intéressantes pour cette division, que je ne comprends pas très bien. Cependant, il y a plusieurs nombres magiques qui pourraient être utilisés – celui-ci arrive à minimiser l’erreur dans la mantisse.
Le nombre magique corrige également les exposants pairs / impairs; l’article mentionne que vous pouvez également trouver d’autres nombres magiques à utiliser.
Ressources
Il y a d’autres discussions sur reddit (utilisateur pb_zeppelin) et slashdot:
- http://games.slashdot.org/article.pl?sid=06/12/01/184205 et mon commentaire
Autres articles de Cette Série
- Systèmes Numériques et Bases
- Le Guide Rapide des GUID
- Comprendre La Racine Carrée Inverse Rapide de Quake
- Une Introduction Simple Aux Réseaux Informatiques
- Permuter deux variables en utilisant XOR
- Comprendre Grand et Petit Ordre des octets Endian
- Unicode et Vous
- Un peu brouillon sur les formats de fichiers binaires
- Algorithmes de tri