Utilisateur:Spitfire06/Brouillon

Cette page est un brouillon appartenant à Spitfire06

Conseils de rédaction

→ N'hésitez pas à publier sur le brouillon un texte inachevé et à le modifier autant que vous le souhaitez.
→ Pour enregistrer vos modifications au brouillon, il est nécessaire de cliquer sur le bouton bleu : « Publier les modifications ». Il n'y a pas d'enregistrement automatique.

Si votre but est de publier un nouvel article, votre brouillon doit respecter les points suivants :

Respectez le droit d'auteur en créant un texte spécialement pour Wikipédia en français (pas de copier-coller venu d'ailleurs).
Indiquez les éléments démontrant la notoriété du sujet (aide).
Liez chaque fait présenté à une source de qualité (quelles sources – comment les insérer).
Utilisez un ton neutre, qui ne soit ni orienté ni publicitaire (aide).
Veillez également à structurer votre article, de manière à ce qu'il soit conforme aux autres pages de l'encyclopédie (structurer – mettre en page).

→ Si ces points sont respectés, pour transformer votre brouillon en article, utilisez le bouton « publier le brouillon » en haut à droite. Votre brouillon sera alors transféré dans l'espace encyclopédique.

Page Racine carrée inverse rapide en cours de trad

Fonctionnement de l'algorithme[modifier | modifier le code]

L'algorithme calcule $1/ \sqrt x$ en effectuant les étapes suivantes :

Transforme l'argument x en entier afin d'appliquer une approximation de $log 2 (x)$
Utilise cet entier pour calculer une approximation de $log 2 (1/ \sqrt 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[modifier | modifier le code]

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

{\begin{aligned}x&=\pm 1.b_{1}b_{2}b_{3}\ldots \times 2^{e_{x}}\\&=\pm 2^{e_{x}}(1+m_{x})\end{aligned}}

Où l'exposant $e x$ est un entier, $m x \in [0, 1)$ , et $1.b 1 b 2 b 3 ...$ est la représentation binaire de la "mantisse" $(1 + m x)$ . Notons qu'il n'est pas nécessaire d'enregistrer le bit avant le point dans la mantisse car il vaut toujours 1. Avec ce formalisme, on calcule 3 entiers :

$S x$ , le "bit de signe", valant 0 si $x > 0$ ou 1 si $x < 0$ (1 bit)
$E x = e x + B$ est "l'exposant biaisé" où $B = 127$ est le "biais d'exposant" (en)^[1] (8 bits)
$M x = m x \times L$ , où $L = 2 23$ ^[2] (23 bits)

Ces valeurs sont ensuite condensées de gauche à droite dans un conteneur 32 bit.

Par exemple, en utilisant le nombre $x = 0.15625 = 0.00101 2$ . En normalisant $x$ on a :

x=+2^{-3}(1+0.25)

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

$S = 0$
$E = -3 + 127 = 124 = 01111100 2$
$M = 0.25 \times 2 23 = 2097152 = 01000000000000000000000 2$

Ces champs sont condensés comme ceci :

Approcher un logarithme en passant à l'entier[modifier | modifier le code]

S'il fallait calculer $1/ \sqrt x$ sans un ordinateur ou une calculatrice, une table de logarithmes serait utile accompagnée de l'identité $log b (1/ \sqrt x) = -½ log b (x)$ valide quelle que soit la base $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 float32 à un entier. Explications :

Soit $x$ un nombre normal positif :

x=2^{e_{x}}(1+m_{x})

On a alors

\log _{2}(x)=e_{x}+\log _{2}(1+m_{x})

Mais puisque $m x \in [0, 1)$ , le logarithme de la partie droite peut être arrondi par^[3]

\log _{2}(1+m_{x})\approx m_{x}+\sigma

où $σ$ est un paramètre arbitraire permettant de régler l'arrondi. Par exemple : $σ = 0$ fournit des résultats exacts aux bords de l'intervalle tandis que $σ \approx 0.0430357$ fournit l'approximation optimale.

Alors nous avons l'approximation

\log _{2}(x)\approx e_{x}+m_{x}+\sigma .

D'un autre côté, en interprétant la réprésentation binaire de $x$ en tant qu'entier, on obtient :^[4]

{\begin{aligned}I_{x}&=E_{x}L+M_{x}\\&=L(e_{x}+B+m_{x})\\&\approx L\log _{2}(x)+L(B-\sigma ).\end{aligned}}

On remarque alors que $I x$ est un approximation linéaire mise à l'échelle et décalée de $log 2 (x)$ , comme présenté sur le graphique ci-contre. En d'autres termes, $log 2 (x)$ est approché par

\log _{2}(x)\approx {\frac {I_{x}}{L}}-(B-\sigma ).

Première approximation du résultat[modifier | modifier le code]

Le calcul de $y = 1/ \sqrt x$ est basé sur l'identité

\log _{2}(y)=-{\frac {1}{2}}\log _{2}(x)

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

I_{y}\approx {\frac {3}{2}}L(B-\sigma )-{\frac {1}{2}}I_{x}

Qui s'écrit en code C :

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

Le premier terme étant le nombre magique

{\frac {3}{2}}L(B-\sigma )={\text{0x5f3759df}}

à partir duquel on déduit $σ \approx 0.0450466$ . Le second terme, $½ I x$ est déterminé en décalant à droite une fois les bits de $I x$ .^[5]

Méthode de Newton[modifier | modifier le code]

Article principal : Méthode de Newton.

Après avoir appliqué ces opérations, l'algorithme considère de nouveau le mot double comme nombre flottant (y = *(float*)&i;) et effectue une multiplication en nombre flottant (y = y*(1.5f - xhalf*y*y);). 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 :

y={\frac {1}{\sqrt {x}}}

est la racine carrée inverse, ou encore, en fonction de y :

f(y)={\frac {1}{y^{2}}}-x=0

.

Avec

y_{n+1}=y_{n}-{\frac {f(y_{n})}{f'(y_{n})}}

représentant l'expression générale de la méthode de Newton avec

\,y_{n}

comme première approximation,

y_{n+1}={\frac {y_{n}(3-xy_{n}^{2})}{2}}

est l'expression particulière où

f(y)={\frac {1}{y^{2}}}-x

et

f'(y)={\frac {-2}{y^{3}}}

.

Ainsi y = y*(1.5f - xhalf*y*y); est semblable à

\,y_{n+1}=y_{n}(1.5-{\frac {xy_{n}^{2}}{2}})={\frac {y_{n}(3-xy_{n}^{2})}{2}}

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 ( $y_{n+1}$ ) comme argument pour l'itération suivante fait converger l'algorithme sur la racine avec une incertitude de plus en plus faible.^[6] Une seule itération a été utilisée dans le cadre du moteur de Quake III, une seconde itération ayant été commentée et laissée.

↑ $E x$ doit être dans le domaine $[1, 254]$ afin que $x$ soit représentable comme un nombre normal (en)
↑ Les seuls réels pouvant être représentés exactement comme des nombres à virgule flottante sont ceux pour lesquels $M x$ est un entier. Les autres nombres ne peuvent être représentés que de façon approchée en les arrondissant au nombre représentable le plus proche.
↑ (en) Charles McEniry, « The Mathematics Behind the Fast Inverse Square Root Function Code », sur daxia.com, août 2007 (consulté le 13 février 2009), p. 3
↑ $S x = 0$ puisque $x > 0$ .
↑ Hennessey & Patterson 1998, p. 305.
↑ (en) Charles McEniry, « The Mathematics Behind the Fast Inverse Square Root Function Code », sur daxia.com, août 2007 (consulté le 13 février 2009), p. 6

[1] $E x$ doit être dans le domaine $[1, 254]$ afin que $x$ soit représentable comme un nombre normal (en)

[2] Les seuls réels pouvant être représentés exactement comme des nombres à virgule flottante sont ceux pour lesquels $M x$ est un entier. Les autres nombres ne peuvent être représentés que de façon approchée en les arrondissant au nombre représentable le plus proche.

[3] (en) Charles McEniry, « The Mathematics Behind the Fast Inverse Square Root Function Code », sur daxia.com, août 2007 (consulté le 13 février 2009), p. 3

[4] $S x = 0$ puisque $x > 0$ .

[5] Hennessey & Patterson 1998, p. 305.

[6] (en) Charles McEniry, « The Mathematics Behind the Fast Inverse Square Root Function Code », sur daxia.com, août 2007 (consulté le 13 février 2009), p. 6

[1]

[2]

[3]

[4]

[5]

[6]