GeeksforGeeks

La racine carrée inverse rapide est un algorithme qui estime , la réciproque (ou l’inverse multiplicatif) de la racine carrée d’un nombre à virgule flottante x de 32 bits au format à virgule flottante IEEE 754. Le calcul des racines carrées réciproques est nécessaire dans de nombreuses applications, telles que la normalisation vectorielle dans les jeux vidéo et est principalement utilisé dans les calculs impliqués dans la programmation 3D. Dans les graphiques 3D, des normales de surface, des vecteurs à 3 coordonnées de longueur 1 sont utilisés pour exprimer l’éclairage et la réflexion. Il y avait beaucoup de normales de surface. Et les calculer implique de normaliser beaucoup de vecteurs. La normalisation n’est souvent qu’un terme de fantaisie pour la division. Le théorème de Pythagore calcule la distance entre les points, et la division par la distance aide à normaliser les vecteurs:

Cet algorithme est surtout connu pour sa mise en œuvre en 1999 dans le code source du jeu Quake III Arena, un jeu vidéo de tir à la première personne qui a fait un usage intensif des graphismes 3D. À cette époque, il était généralement coûteux de calculer la réciproque d’un nombre à virgule flottante, en particulier à grande échelle; la racine carrée inverse rapide a contourné cette étape.Algorithme

:
Étape 1: Il réinterprète les bits de l’entrée à virgule flottante sous la forme d’un entier.

i = * ( long * ) &y; 

Étape 2: Il prend la valeur résultante et effectue une arithmétique entière dessus, ce qui produit une approximation de la valeur que nous recherchons.

i = 0x5f3759df - ( i >> 1 );

Étape 3: Le résultat n’est pas l’approximation elle-même, mais c’est un entier qui se trouve être, si vous réinterprétez les bits comme un nombre à virgule flottante, l’approximation. Ainsi, le code fait l’inverse de la conversion à l’étape 1 pour revenir à la virgule flottante:

y = * ( float * ) &i;

Étape 4: Et enfin, il exécute une seule itération de la méthode de Newton pour améliorer l’approximation.

y = y * ( threehalfs - ( x2 * y * y ) ); //threehalfs = 1.5F;

L’algorithme accepte un nombre à virgule flottante de 32 bits en entrée et stocke une valeur divisée par deux pour une utilisation ultérieure. Ensuite, en traitant les bits représentant le nombre à virgule flottante comme un entier de 32 bits, un décalage logique d’un bit vers la droite est effectué et le résultat est soustrait du nombre magique 0x5F3759DF. C’est la première approximation de la racine carrée inverse de l’entrée. En traitant à nouveau les bits comme un nombre à virgule flottante, il exécute une itération de la méthode d’approximation de Newton, donnant une approximation plus précise.

Disons qu’il existe un nombre sous forme d’exposant ou de notation scientifique:
=100 million
Maintenant, pour trouver la racine carrée régulière, il suffit de diviser l’exposant par 2:

Et si, vous voulez connaître la racine carrée inverse, divisez l’exposant par -2 pour inverser le signe:

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, aka 5 dans: 5 · ), gère les exposants pairs impairs, déplaçant des bits de l’exposant dans la mantisse, et toutes sortes de trucs géniaux.

Le code suivant est l’implémentation rapide de la racine carrée inverse de Quake III Arena (commentaire original exact écrit dans le jeu Quake III Arena).

Sortie: