Voir la source de Racine carrée inverse rapide

[[Fichier:OpenArena-Rocket.jpg|vignette|droite|Les calculs de lumière (ici dans ''[[OpenArena]]'', un [[Fork (développement logiciel)|fork]] de ''{{lnobr rom|Quake III Arena}}'') utilisent la racine carrée inverse rapide pour calculer les angles d'[[Angle d'incidence (optique)|incidence]] et de [[Réflexion (optique)|réflexion]].]]

La '''racine carrée inverse rapide''' (en anglais '''''{{Langue|en|fast inverse square root}}''''', parfois abrégé '''Fast InvSqrt()''' ou par la constante '''0x5f3759df''' en [[Système hexadécimal|hexadécimal]]) est une méthode pour calculer {{math|''x''<sup>−½</sup>}}, aussi notée {{math|{{sfrac|1|{{racine|''x''}}}}}}, l'[[inverse]] de la [[racine carrée]] d'un nombre à [[Virgule flottante simple précision|virgule flottante à simple précision]] sur {{nobr|32 bits}}. L'[[algorithme]] a probablement été développé chez [[Silicon Graphics]] au début des années {{date|1990}}. Il a entre autres été utilisé dans le code source de ''{{lnobr rom|Quake III Arena}}'', un [[jeu vidéo]] de [[jeu de tir à la première personne|tir à la première personne]] sorti en {{date|1999}}{{sfn|Sommefeldt|nov. 2006}}. À l'époque, le principal avantage de cet algorithme était d'éviter des [[Opération (mathématiques)|opérations]] en [[virgule flottante]], coûteuses en [[puissance de calcul]], en préférant des opérations sur [[Entier (informatique)|entiers]]. Les racines carrées inverses sont utilisées pour calculer les [[Angle d'incidence (optique)|angles d'incidence]] et la [[Réflexion (optique)|réflexion]] pour la lumière et l'ombre en [[imagerie numérique]].

L'algorithme prend en entrée des flottants de {{nobr|32 bits}} non signés et stocke la moitié de cette valeur pour l'utiliser plus tard. Ensuite, il traite le nombre à virgule flottante comme un entier et lui applique un [[décalage logique]] à droite d'un bit et le résultat est soustrait à la valeur « magique » 0x5f3759df. Il en résulte une première approximation de la racine carrée inverse du nombre passé en entrée. En considérant de nouveau les bits comme un nombre à virgule flottante et en appliquant au nombre la [[méthode de Newton]], on améliore cette approximation. Bien que n'assurant pas la [[Précision arithmétique|précision]] la plus fine possible, le résultat final est une approximation acceptable de la racine carrée inverse d'un nombre à virgule flottante qui s'exécute quatre fois plus vite qu'une division d'un tel nombre.

== Motivation ==
[[Fichier:Surface normal.png|vignette|Les [[Normale à une surface|normales à une surface]] sont largement utilisées dans les calculs d'éclairage et d'ombrage, ce qui nécessite le calcul des normes des vecteurs. Ici, on montre un champ de vecteurs normaux à la surface.]]

Les racines carrées inverses d'un nombre à virgule flottante sont utilisées pour calculer un [[Vecteur unitaire|vecteur normalisé]]<ref>{{Ouvrage |langue=en |auteur1=[[Jim Blinn]] |titre=Jim Blinn's Corner |sous-titre=Notation, Notation, Notation |lieu=Amsterdam/Boston |éditeur=Morgan Kaufmann |année=2003 |pages totales=327 |isbn=1-55860-860-5 |passage=130 {{lire en ligne|url={{Google Livres|vEHb-8yWbG0C|page=130}}}}}}.</ref>. En [[Infographie tridimensionnelle|synthèse d'image 3D]], ces vecteurs normalisés sont utilisés pour déterminer l'éclairage et l'ombrage. Des millions de ces calculs sont ainsi nécessaires chaque seconde. Avant l'apparition de matériel dédié au [[Transform, clipping, and lighting|TCL]], ces calculs pouvaient être lents. Ce fut particulièrement le cas lorsque cette technique a été développée au début des années {{date|1990}} où les opérations sur les nombres à virgule flottante étaient plus lentes que les calculs sur entiers{{sfn|Sommefeldt|nov. 2006}}.

Afin de normaliser un vecteur, on détermine la longueur de celui-ci en calculant sa [[Norme (mathématiques)|norme euclidienne]] : la racine carrée de la somme du carré de ses [[Composantes d'un vecteur|composantes]]. Après avoir divisé chaque composante par cette longueur, on obtient alors un nouveau [[vecteur unitaire]] pointant dans la même direction.

:<math>\|\boldsymbol{v}\| = \sqrt{v_1^2+v_2^2+v_3^2}</math> est la norme euclidienne du vecteur, de la même manière que l'on calcule une distance dans un [[espace euclidien]].

:<math>\boldsymbol{\hat{v}} = \boldsymbol{v} / \|\boldsymbol{v}\|</math> est le vecteur (unitaire) normalisé. Avec <math>\|\boldsymbol{v}\|^2</math> représentant <math>v_1^2+v_2^2+v_3^2</math>,

:<math>\boldsymbol{\hat{v}} = \boldsymbol{v} / \sqrt{\|\boldsymbol{v}\|^2}</math>, liant le vecteur unitaire à la racine carrée inverse des composantes.

== Aperçu du code ==
Le [[code source]] suivant est celui de la [[Fonction informatique|fonction]] <code>Q_rsqrt</code> qui implémente la racine carrée inverse rapide dans ''{{lnobr rom|Quake III Arena}}''. On a retiré du code les directives du {{lnobr|préprocesseur C}} ([[Ligne de code|lignes]] commençant par <code>#</code>), mais on a laissé les [[Commentaire (informatique)|commentaires]] originaux (introduits par <code>//</code>)<ref>{{lien web|langue=en|url=https://github.com/id-Software/Quake-III-Arena/blob/master/code/game/q_math.c|auteur1=
Travis Bradshaw |titre=code/game/q_math.c|série=The {{nobr romains|Quake III}} Arena sources as originally released under the GPL license on August 20, 2005|éditeur=[[id Software]] |site=[[GitHub]]|date=31 janvier 2012}}, lignes 552 à 572.</ref>.<!--
Le « fuck » fait partie des commentaires originaux ; merci de ne pas le retirer. -->
<syntaxhighlight lang="c">
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

	return y;
}
</syntaxhighlight>

Afin de déterminer la racine carrée inverse, un programme calculerait une approximation de {{math|''x''<sup>−½</sup>}} puis appliquerait ensuite une [[méthode numérique]] afin de peaufiner le résultat jusqu'à atteindre une [[erreur d'approximation]] acceptable. Des méthodes d'[[extraction de racine carrée]] du début des années {{date|1990}} ont permis d'avoir une première approximation depuis une [[table de correspondance]]<ref>{{Ouvrage |langue=en |auteur1=David H. Eberly |titre=3D Game Engine Design |sous-titre=A Practical Approach to Real-Time Computer Graphics |lieu=San Francisco |éditeur=Morgan Kaufmann |année=2001 |pages totales={{XXVIII}}-561 |isbn=1-55860-593-2 |numéro chapitre=B.8.1 |titre chapitre=Square Root and Inverse Square Root |passage=503–504}} ; {{2e|{{éd.}}}} Amsterdam, Boston, [[Elsevier]]/Morgan Kaufmann, {{date|2007}}, {{XXII}}-1018{{nb p.}} {{ISBN|978-0-12-229063-3<!-- version imprimée -->|978-0-12-373668-0<!-- CD-ROM avec la version imprimée -->|978-0-08-091799-3<!-- numérique -->|978-1-4822-6730-3<!-- numérique -->}} {{DOI|10.1016/B978-0-12-229063-3.50020-0}}, {{chap.|16.8.1}}, {{p.|754–755}} {{lire en ligne|url={{Google Livres|TnwZBwAAQBAJ|page=754}}}}.</ref>. Cette nouvelle fonction s'est montrée plus efficace que les tables de correspondance et environ quatre fois plus rapide qu'une division flottante classique{{sfn|Lomont|2003|p=1}}. L'algorithme a été conçu selon la norme {{lnobr|IEEE 754}}<ref group="alpha">[[IEEE 754]].</ref> pour les nombres à [[virgule flottante]] {{nobr|32 bits}}, mais des recherches de Chris Lomont et ensuite Charles McEniry ont montré qu'il pouvait être implémenté en utilisant d'autres spécifications de nombres à virgule flottante.

Le gain de vitesse apporté par le [[kludge]] qu'est la racine carrée inverse rapide vient du traitement du [[Mot (architecture informatique)|mot]] double<ref group=alpha>L'utilisation du type <code>long</code> réduit la [[Portabilité (informatique)|portabilité]] de ce code sur les systèmes récents. Afin que le code s'exécute, <code>sizeof(long)</code> doit valoir 4 [[octet]]s sinon la fonction risque de retourner des résultats négatifs. Sur les [[Processeur 64 bits|systèmes {{nobr|64 bits}}]] récents, <code>sizeof(long)</code> vaut {{nobr|8 octets}}.</ref> contenant le nombre à virgule flottante considéré comme entier qui est ensuite soustrait à une constante spécifique : '''0x5f3759df'''. L'utilité de cette constante n'étant pas claire à première vue, on la considère alors comme un [[Nombre magique (programmation)#Constantes numériques non nommées|nombre magique]]{{sfn|Sommefeldt|nov. 2006}}{{,}}{{sfn|Lomont|2003|p=3}}{{,}}{{sfn|McEniry|2007|p=1}}{{,}}{{sfn|Eberly|2001|p=2}}. Après cette [[soustraction]] d'entiers et ce décalage à droite, on obtient un mot double qui, lorsqu'il est considéré comme un nombre à virgule flottante, devient une approximation grossière de la racine carrée inverse du nombre entré. Ensuite, une [[itération]] de la [[méthode de Newton]] est réalisée afin de gagner en précision et le résultat est retourné. L'algorithme génère des résultats raisonnablement précis en utilisant une seule approximation par la méthode de Newton ; toutefois, il reste plus lent que d'utiliser <tt>rsqrtss</tt>, une [[Instruction informatique|instruction]] du jeu [[Streaming SIMD Extensions|SSE]], sortie elle aussi en {{date|1999}} sur les processeurs [[x86]]<ref name="ruskin">{{Lien archive |langue=en |auteur=Elan Ruskin |titre=Timing Square Root |site=assemblyrequired.crashworks.org |date=16 octobre 2009 |horodatage archive=20210415133719 |url=http://assemblyrequired.crashworks.org/timing-square-root/}}.</ref>.

=== Exemple pratique ===

Considérons un nombre {{math|''x'' {{=}} 0,156 25}}, pour lequel on souhaite calculer {{math|{{sfrac|1|{{racine|''x''}}}} ≈ 2,529 82}}. Voici les premières étapes de l'algorithme :

 0011_1110_0010_0000_0000_0000_0000_0000  Trame binaire de x et i
 0001_1111_0001_0000_0000_0000_0000_0000  Décalage à droite d'une position : (i &gt;&gt; 1)
 0101_1111_0011_0111_0101_1001_1101_1111  Le nombre magique 0x5f3759df
 0100_0000_0010_0111_0101_1001_1101_1111  le résultat de 0x5f3759df - (i &gt;&gt; 1)

En utilisant la représentation IEEE 754 sur {{nobr|32 bits}} :

 0_01111100_01000000000000000000000  1.25 * 2^-3
 0_00111110_00100000000000000000000  1.125 * 2^-65
 0_10111110_01101110101100111011111  1.432430... * 2^+63
 0_10000000_01001110101100111011111  1.307430... * 2^+1

En réinterprétant la dernière trame binaire en tant que nombre à virgule flottante on obtient l'approximation {{math|''y'' {{=}} 2,614 86}} ayant une erreur relative d'environ 3,4 %. Après une itération de la méthode de Newton, le résultat final est {{math|y {{=}} 2,525 49}} avec une erreur de seulement 0,17 %.

== Fonctionnement de l'algorithme ==

L'algorithme calcule {{math|{{sfrac|1|{{racine|''x''}}}}}} en effectuant les étapes suivantes :

# Transforme l'argument {{math|''x''}} en entier afin d'appliquer une approximation de {{math|log<sub>2</sub>(''x'')}} ;
# Utilise cet entier pour calculer une approximation de {{math|log<sub>2</sub>({{sfrac|1|{{racine|''x''}}}})}} ;
# Transforme celui-ci afin de revenir à un nombre flottant afin d'effectuer une approximation de l'exponentielle base-2 ;
# Affine l'approximation en utilisant une itération de la méthode de Newton.

=== Représentation en nombre flottant ===

Puisque cet algorithme s'appuie fortement sur la représentation bit à bit des nombres à virgule flottante simple précision, un aperçu rapide de ce système est fourni ici. Afin d'encoder un nombre réel non nul {{math|''x''}} en tant que flottant de simple précision, on commence par écrire {{math|''x''}} comme un nombre binaire en [[notation scientifique]] :

:<math>\begin{align}
x &= \pm 1,b_1b_2b_3\ldots \times 2^{e_x}\\
  &= \pm 2^{e_x} (1 + m_x)
\end{align}</math>

Où l'exposant {{math|''e<sub>x</sub>''}} est un entier, {{math|''m<sub>x</sub>'' ∈ [0, 1)}}, et {{math|1,b<sub>1</sub>b<sub>2</sub>b<sub>3</sub>...}} est la représentation binaire de la « [[mantisse]] » {{math|(1 + ''m<sub>x</sub>'')}}. Notons qu'il n'est pas nécessaire d'enregistrer le bit avant la virgule dans la mantisse car il vaut toujours 1. Avec ce formalisme, on calcule trois entiers :

* {{math|''S<sub>x</sub>''}}, le « [[bit de signe]] », valant 0 si {{math|''x'' &gt; 0}} ou 1 si {{math|''x'' &lt; 0}} ({{nobr|1 bit}}) ;
* {{math|''E<sub>x</sub>'' {{=}} ''e<sub>x</sub>'' + ''B''}} est l'« exposant biaisé » où {{math|''B'' {{=}} 127}} est le {{Lien|trad=Exponent bias|fr=Biais d'exposant|texte=« biais d'exposant »}}<ref group=alpha>{{math|''E<sub>x</sub>''}} doit être dans le domaine {{math|[1, 254]}} afin que {{math|''x''}} soit représentable comme un {{Lien|Normal number (computing)|lang=en|texte=nombre normal}}.</ref> ({{nobr|8 bits}}) ;
* {{math|''M<sub>x</sub>'' {{=}} ''m<sub>x</sub>'' × ''L''}}, où {{math|''L'' {{=}} 2<sup>23</sup>}} <ref group=alpha>Les seuls [[Nombre réel|réels]] pouvant être représentés ''exactement'' comme des nombres à virgule flottante sont ceux pour lesquels {{math|''M<sub>x</sub>''}} est un entier. Les autres nombres ne peuvent être représentés que de façon approchée en les [[Arrondi (mathématiques)|arrondissant]] au nombre représentable le plus proche.</ref> ({{nobr|23 bits}}).

Ces valeurs sont ensuite condensées de gauche à droite dans un conteneur {{nobr|32 bits}}.

Par exemple, en utilisant le nombre {{math|''x'' {{=}} 0,156 25 {{=}} 0,001 01<sub>2</sub>}}. En normalisant {{math|''x''}} on a :

:<math>x = +2^{-3}(1 + 0,25)</math>

Donc, les trois valeurs entières non signées sont :

* {{math|''S'' {{=}} 0}} ;
* {{math|''E'' {{=}} −3 + 127 {{=}} 124 {{=}} 01111100<sub>2</sub>}} ;
* {{math|''M'' {{=}} 0,25 × 2<sup>23</sup> {{=}} 2097152 {{=}} 01000000000000000000000<sub>2</sub>}}.

Ces champs sont condensés comme ceci :

[[Fichier:Float w significand 2.svg|centré]]

=== Approcher un logarithme en passant à l'entier ===

S'il fallait calculer {{math|{{sfrac|1|{{racine|''x''}}}}}} sans un ordinateur ou une calculatrice, une [[table de logarithmes]] serait utilement accompagnée de l'identité {{math|log<sub>b</sub>({{sfrac|1|{{racine|''x''}}}}) {{=}} −{{sfrac|1|2}} log<sub>b</sub>(''x'')}} valide quelle que soit la base {{math|''b''}}. La racine carrée inverse rapide repose sur cette dernière ainsi que sur le fait que l'on puisse effectuer un [[logarithme]] approximatif d'un nombre en passant d'un [[Virgule flottante simple précision|float32]] à un entier. 

Explications :

Soit {{math|''x''}} un {{Lien|Normal number (computing)|lang=en|texte=nombre normal}} positif :

:<math>x = 2^{e_x} (1 + m_x)</math>

On a alors

:<math>\log_2(x) = e_x + \log_2(1 + m_x)</math>

Mais puisque {{math|''m<sub>x</sub>'' ∈ [0, 1)}}, le logarithme de la partie droite peut être arrondi par{{sfn|McEniry|2007|p=3}} :
:<math>\log_2(1 + m_x) \approx m_x + \sigma</math>

où {{math|σ}} est un paramètre arbitraire permettant de régler l'arrondi. Par exemple : {{math|σ {{=}} 0}} fournit des résultats exacts aux bords de l'intervalle tandis que {{math|σ ≈ 0.0430357}} fournit l'[[Théorie de l'approximation|approximation optimale]].

[[Fichier:Log_by_aliasing_to_int.svg|vignette|L'entier converti en nombre flottant (en bleu), comparé à un logarithme décalé et mis à l'échelle (en gris).]]

Alors nous avons l'approximation

:<math>\log_2(x) \approx e_x + m_x + \sigma.</math>

D'un autre côté, en interprétant la représentation binaire de {{math|''x''}} en tant qu'entier, on obtient<ref group="alpha">{{math|''S<sub>x</sub>'' {{=}} 0}} puisque {{math|''x'' &gt; 0}}.</ref> :

:<math>\begin{align}
I_x &= E_x L + M_x\\
    &= L (e_x + B + m_x)\\
    &\approx L \log_2(x) + L (B - \sigma).
\end{align}</math>

On remarque alors que {{math|''I<sub>x</sub>''}} est une approximation linéaire mise à l'échelle et décalée de {{math|log<sub>2</sub>(''x'')}}, comme présenté sur le graphique ci-contre. En d'autres termes, {{math|log<sub>2</sub>(''x'')}} est approché par

:<math>\log_2(x) \approx \frac{I_x}{L} - (B - \sigma).</math>

=== Première approximation du résultat ===
Le calcul de {{math|''y'' {{=}} {{sfrac|1|{{racine|''x''}}}}}} est fondé sur l'identité

:<math>\log_2(y) = - \frac{1}{2}\log_2(x)</math>

En utilisant l'approximation du logarithme telle que précédemment définie et appliquée à {{math|''x''}} et {{math|''y''}}, l'équation devient :

:<math>I_y \approx \frac{3}{2} L (B - \sigma) - \frac{1}{2} I_x</math>

Qui s'écrit en code [[C (langage)|C]] :

<syntaxhighlight lang="c">
i = 0x5f3759df - ( i >> 1 );
</syntaxhighlight>

Le premier terme étant le nombre magique

:<math>\frac{3}{2} L (B - \sigma) = \text{0x5f3759df}</math>

à partir duquel on déduit {{math|σ ≈ 0,045 046 6}}. Le second terme, {{math|{{sfrac|1|2}} ''I<sub>x</sub>''}}, est déterminé en décalant à droite une fois les bits de {{math|''I<sub>x</sub>''}}<ref>{{ouvrage |langue=en |auteur1=[[John L. Hennessy]] |auteur2=[[David A. Patterson]] |titre=Computer Organization and Design |sous-titre=The Hardware-Software Interface |numéro d'édition=2 |lieu=San Francisco |éditeur=Morgan Kaufmann |année=1998 |isbn=1-55860-491-X<!-- paper --> |isbn2=1-55860-428-6<!-- cloth --> |passage=305}}.</ref>.

=== Méthode de Newton ===
{{Article principal|Méthode de Newton}}
{{Multiple image
| align =
| direction = vertical
| total_width =
| image1 = First initial approximate value.png
| image2 = Relative error between Fast inverse square root and 1-sqrt().png
| image3 = 2nd-iter.png
| image4 = 3rd-iter.png
| image5 = 4th-iter.png
| image_gap = 0
| footer = [[Erreur relative]] entre calcul direct et racine carrée inverse rapide, en exécutant (de haut en bas) 0, 1, 2, 3 et {{nobr|4 itérations}} de la méthode de Newton (calculs effectués en double précision, la plus petite différence représentable entre {{nobr|2 nombres}} en double précision étant atteinte en {{nobr|4 itérations}}).
}}

Après avoir appliqué ces opérations, l'algorithme considère de nouveau le mot double comme nombre flottant ({{nobr|1=<code>y = *(float*)&i;</code>}}) et effectue une multiplication en nombre flottant ({{nobr|1=<code>y = y*(1.5f - xhalf*y*y);</code>}}). Celle-ci étant une itération de la méthode de Newton permettant de trouver des solutions à une équation donnée. Pour ce même exemple :

:<math>y=\frac{1}{\sqrt{x}}</math> est la racine carrée inverse, ou encore, en fonction de y :

:<math>f(y)=\frac{1}{y^2}-x=0</math>.

:Avec <math>y_{n+1} = y_{n} - \frac{f(y_n)}{f'(y_n)}</math> représentant l'expression générale de la méthode de Newton avec <math>\, y_n</math> comme première approximation,

:<math>y_{n+1} = \frac{y_{n}(3-xy_n^2)}{2}</math> est l'expression particulière où <math>f(y)=\frac{1}{y^2}-x</math> et <math>f'(y)=\frac{-2}{y^3}</math>.

:Ainsi <code>y = y*(1.5f - xhalf*y*y);</code> est semblable à <math>\, y_{n+1} = y_{n}(1.5-\frac{xy_n^2}{2}) = \frac{y_{n}(3-xy_n^2)}{2}</math>

La première approximation est générée en utilisant les opérations en tant qu'entiers puis fournie aux deux dernières lignes de code de la fonction. Des itérations répétées de cet algorithme en utilisant la sortie de la fonction (<math>y_{n+1}</math>) comme argument pour l'itération suivante fait converger l'algorithme sur la racine avec une incertitude de plus en plus faible{{sfn|McEniry|2007|p=6}}. Une seule itération a été utilisée dans le cadre du [[Id Tech 3|moteur de ''{{nobr romains|Quake III}}'']], une seconde itération ayant été commentée et laissée.

== Histoire et enquête ==

{{Détail image
|image = Carmack at QuakeCon 2002 - 05.jpg
|largeur initiale = 420
|largeur détail = 180
|hauteur détail = 230
|point haut = 50
|point gauche = 125
|position = gauche
|légende=[[John Carmack]], cofondateur d'[[id Software]], est souvent associé à cette fonction, même s'il ne l'a pas écrite.
}}

Le code source de ''{{lnobr rom|Quake III Arena}}'' a été diffusé après la [[QuakeCon]] {{date|2005}}, mais des copies de la racine carrée inverse rapide sont apparues sur [[Usenet]] et d'autres forums dès {{date|2002}}/{{date|2003}}{{sfn|Sommefeldt|nov. 2006}}. Les spéculations à l'époque pointent comme auteur probable de la fonction [[John Carmack]], cofondateur d'[[id Software]], l'entreprise qui a [[Développeur de jeux vidéo|développé]] les jeux ''[[Quake]]''. Mais Carmack dément la chose et suggère que la fonction a été écrite par Terje Mathisen, un programmeur [[assembleur]] talentueux qui a aidé les développeurs d'id Software pour optimiser ''Quake''. Mathisen a effectivement écrit une fonction similaire à la fin des années {{date|1990}}, mais les auteurs originaux remontent à plus loin dans l'histoire de l'infographie 3D avec l'implémentation faite par Gary Tarolli pour un {{Lien|langue=en|fr=SGI Indigo}} qui serait l'une des premières utilisations connues. Rys Sommefeldt, auteur de l'enquête, finit par conclure que l'algorithme original est l'œuvre de Greg Walsh de {{Lien|langue=en|fr=Ardent Computer}} en collaboration avec [[Cleve Moler]], fondateur de [[The MathWorks|MathWorks]]{{sfn|Sommefeldt|déc. 2006}}.

On ne sait pas comment la valeur exacte du nombre magique a été déterminée. Chris Lomont a développé une fonction pour minimiser l'[[erreur d'approximation]] en choisissant le nombre magique ''R'' dans un intervalle. Il calcule d'abord la constante optimale pour l'étape d'approximation linéaire, il obtient '''0x5f37642f''' qui est proche de '''0x5f3759df''', mais avec cette nouvelle constante, il obtient une précision moindre après une itération de la méthode de Newton{{sfn|Lomont|2003|p=10}}. Il cherche alors une constante optimale même après une ou deux itérations de la méthode de Newton et obtient la valeur '''0x5f375a86''' qui se révèle plus précise que l'originale, même après chaque étape d'itération{{sfn|Lomont|2003|p=10}}. Il conclut alors en se demandant si la valeur originale a été choisie par dérivation ou par [[essai-erreur]]{{sfn|Lomont|2003|p=10–11}}. Dans la lancée, Lomont indique aussi que la valeur magique pour flottant double précision {{nobr|64 bits}} {{lnobr|IEEE 754}} est '''0x5fe6ec85e7de30da''', mais il a été démontré que la valeur exacte était '''0x5fe6eb50c7b537a9'''{{sfn|Robertson|2012|p=33}}. Charles McEniry a effectué une optimisation similaire mais plus sophistiquée sur les valeurs probables pour ''R''. Il cherche d'abord par une [[recherche exhaustive|méthode par force brute]] et obtient la valeur déterminée par Lomont{{sfn|McEniry|2007|p=11–12}}. Il a ensuite essayé de rechercher cette valeur par une [[méthode de dichotomie]] et obtient alors la valeur utilisée initialement dans la fonction, ce qui conduit McEniry à penser que cette constante a probablement été obtenue par cette méthode{{sfn|McEniry|2007|p=16}}.

== Notes et références ==
{{Traduction/Référence|en|Fast inverse square root|508816170|type=note}}
=== Notes ===
{{références|groupe=alpha}}

=== Références ===
{{références}}

== Voir aussi ==

=== Bibliographie ===
* {{Lien web |langue=en |auteur=Chris Lomont |titre=Fast Inverse Square Root |site=lomont.org |date=février 2003 |url=http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf |format=pdf |consulté le=13 février 2009}}.
* {{Lien web |langue=en |auteur=Charles McEniry |titre=The Mathematics Behind the Fast Inverse Square Root Function Code |site=daxia.com |date=août 2007 |url=http://www.daxia.com/bibis/upload/406Fast_Inverse_Square_Root.pdf |format=pdf |consulté le=13 février 2009}}.
* {{lien web |langue=en |auteur1=Matthew Robertson |titre={{Langue|en|A Brief History of InvSqrt}} |éditeur=[[Université du Nouveau-Brunswick]] |date=24 avril 2012 |url=https://mrober.io/papers/rsqrt.pdf |format=pdf}}.
* {{lien archive |langue=en |auteur1=Rys Sommefeldt |titre=Origin of Quake3's Fast InvSqrt() |site=Beyond3D.com |date=29 novembre 2006 |horodatage archive=20070317031123 |url=https://www.beyond3d.com/content/articles/8/ |id=Sommefeldtnov. 2006}}.
* {{lien archive |langue=en |auteur1=Rys Sommefeldt |titre=Origin of Quake3's Fast InvSqrt() - Part Two |site=Beyond3D.com |date=19 décembre 2006 |horodatage archive=20070519091708 |url=https://www.beyond3d.com/content/articles/15/ |id=Sommefeldtdéc. 2006}}.

=== Articles connexes ===
* [[Extraction de racine carrée]]

=== Liens externes ===
* {{lien web |langue=en |auteur1=Adam Hyland |url=https://0x5f37642f.com |titre=0x5f37642f.com |description=site consacré à la racine carrée inverse rapide}}.

{{palette|Quake}}
{{portail|informatique|informatique théorique|imagerie numérique|mathématiques|jeu vidéo}}

[[Catégorie:Algorithme de recherche d'un zéro d'une fonction]]
[[Catégorie:Quake]]
[[Catégorie:Code source]]
[[Catégorie:Développement de jeux vidéo]]