En 2005, l’entreprise id Software a publié en open source le code de son jeu mythique Quake III Arena, sorti en 1999. Au milieu du code, une fonction courte, mais totalement ésotérique, prétend calculer l’inverse de la racine carrée d’un nombre réel.
Vous pouvez voir le code ci-dessous, les commentaires sont d’origine !
Le code a des notations un peu perturbantes, en voici une récriture simplifiée mais équivalente, en conservant les savoureux commentaires
Mais qu’est-ce que c’est que ce code ? De la magie noire ? Il prétend calculer l’inverse d’une racine carrée, et il n’y a pas de racine, pas de boucles d’itérations et même pas de divisions ? Juste une poignée d’additions et des multiplications ?
En plein milieu, la ligne diabolique nous nargue :
Le nombre 0x5f3759df est ici codé en hexadécimal, et représente le nombre entier 1597463007. Que fait ce nombre ici ? Est-ce une constante mathématique universelle entretenant un lien mystérieux et profond avec l’idée de racine carrée inverse ?
Alors creusons la sorcellerie qui se cache derrière cet algorithme ! (Et pour ceux qui voudraient essayer eux-même, mon code est sur GitHub)
Un peu d’histoire
Le studio id Software est un pilier de l’histoire du jeu vidéo. Fondé en 1991 par deux légendes du domaine, John Romero et John Carmack, il sera à l’origine de monuments vidéoludiques comme Wolfenstein 3D, Doom ou encore Quake. Ces titres ont été distingués pour leurs qualités techniques, notamment dans le rendu 3D, et ont largement fait la réputation de John Carmack, programmeur en chef de génie d’id Software.
John Carmack a été à l’origine de nombreuses innovations dans les moteurs de jeu vidéo de l’époque, et c’est donc sans surprise que quand le code de Quake III Arena a été open-sourcé, sa mystérieuse “Racine carrée inverse rapide” a été vue comme une nouvelle diablerie d’un Carmack exerçant son art occulte.
Mais nous allons voir que la paternité de cette astuce est plus ancienne, et qu’il est même possible de comprendre son fonctionnement et son élaboration en se penchant sur la manière dont nos ordinateurs manipulent et stockent les nombres.
On trouve ici et là sur Internet pas mal d’explications de cette astuce de la racine carrée inverse, mais aucune que je trouve à la fois complète et totalement à mon goût. J’ai donc décidé de vous proposer la mienne ! Comme c’est un peu long, j’ai décidé de diviser cette histoire en deux.
L’article d’aujourd’hui va être consacré aux deux dernières lignes du code
qui nous permettront de mieux comprendre à quoi servent les 3 lignes du dessus,
et que nous traiterons la prochaine fois.
Mais au fait, avant de se lancer, pourquoi diable vouloir calculer l’inverse de la racine carrée d’un nombre ?
De l’importance de la racine carrée inverse
Dans les moteurs 3D de jeu vidéo, on passe son temps à manipuler des vecteurs tri-dimensionnels. Ceux-ci peuvent représenter des éléments de géométrie, des vitesses d’objets, des directions de propagation, etc. Et il est très fréquent que l’on ait besoin de normaliser ces vecteurs, c’est-à-dire de ramener leur longueur à 1, tout en préservant leur sens et leur direction.
Mathématiquement, c’est assez simple. Si un vecteur est représenté par les trois coordonnées
alors il suffit de calculer la longueur totale du vecteur par le théorème de Pythagore (en 3D)
Puis on divise chaque coordonnée par ce résultat. Le vecteur normalisé est donc simplement
Mathématiquement rien de compliqué. Informatiquement, ça se corse. Il est facile de calculer le nombre
ce ne sont que des additions et des multiplications, qui sont très simples et rapides à faire pour un processeur. Par contre, il faut ensuite diviser chaque coordonnée par la racine carrée de ce nombre. La division est déjà beaucoup plus pénible et coûteuse en CPU, environ 3 à 4 fois plus qu’une addition ou une multiplication. Mais la racine carrée, c’est encore pire !
A la base, il n’existe pas de façon simple de réaliser le calcul d’une racine carrée sur des nombres représentés par des bits. Et même si les processeurs modernes ont maintenant des instructions natives dédiées, ça n’était pas le cas à l’époque de Quake III. Il faut donc écrire du code spécifique, et avoir recours à une méthode approchée et itérative.
Trouver la racine
Une approche simple pour calculer la racine carrée d’un nombre réel, c’est d’utiliser l’algorithme itératif de Newton. L’idée est la suivante : prenons un nombre a dont nous cherchons la racine, c’est-à-dire le nombre x qui obéit à l’équation
Équation que l’on peut aussi récrire
La méthode de Newton est un algorithme permettant de façon générale de trouver une solution approchée d’une équation de la forme f(x) = 0. On va donc l’appliquer ici au cas particulier de la fonction f définie par
L’idée générale de la méthode est la suivante. Si vous cherchez un point x auquel s’annule une fonction f, vous pouvez toujours partir d’une proposition x0 de votre choix, et calculer f(x0) pour voir quelle valeur vous obtenez.
Ce ne sera certainement pas directement 0 ou une valeur proche de 0, mais on va essayer d’itérer pour s’en approcher. La question est de savoir si vous pouvez maintenant proposer une autre valeur x1, qui ait plus de chance de se rapprocher de la solution. Si vous savez calculer la dérivée de f en x0, c’est à dire f’(x0), alors vous pouvez tracer la tangente. La meilleure chose que vous puissiez faire, c’est alors de regarder où est-ce que la droite tangente vaut y=0, et considérer ce point comme votre prochaine tentative.
Vous voyez qu’en faisant ça, on se rapproche de l’objectif, et ce d’autant plus que la courbe de la fonction est “proche” d’être une droite.
Numériquement, je vous laisse vérifier que l’équation de la droite rouge, tangente à la courbe en x0 est
Et donc le point x1 qui est celui où cette droite coupe l’axe horizontal (y=0) est
Et on peut recommencer en ce nouveau point x1 : calculer f et sa dérivée, tracer la tangente, et trouver x2, et ainsi de suite autant de fois qu’on veut. Peu à peu on va se rapprocher de la solution, et on peut décider de s’arrêter au bout d’un certain nombre d’itéarions, ou quand on estime être assez proche.
L’algorithme générique est donc simple : on part d’un x0 qui nous semble raisonnable, et on itère à chauqe étape en calculant un nouveau point avec
Si on sait calculer la valeur de la fonction et de sa dérivée en un point donné, on va converger vers la solution.
Appliquons ça à l’équation qui définit la racine carrée du nombre a
et ça nous fait un algorithme itératif pour calculer la racine carrée de ce nombre.
En voici une petite implémentation, avec une condition d’arrêt des itérations sur le nombre maximum d’itérations et la tolérance.
On remarque que l’itération fait intervenir une division
x += - fx/(2*x)
Et on sait que les divisions c’est coûteux, mais pas moyen de faire autrement.
Notez un élément crucial dans cet algorithme : le point x0 auquel on l’initialise, que j’ai noté “Initial guess”. J’ai choisi de l’initialiser sur la valeur de a lui même. La supposition implicite derrière ce choix, c’est de dire “a n’est pas trop éloigné de racine(a) que l’on cherche”. Ca n’est pas trop mauvais pour de petites valeurs de a, mais plus a devient grand, plus ce choix initial est mauvais, et donc cela demandra plus d’itérations. (J’aurais pu aussi simplement initialiser à 1)
On reviendra sur cette notion de “bien choisir le point de départ”, car elle est essentielle. Mais tout ça c’était pour la racine carrée, revenons à notre racine carrée inverse.
Newton pour la racine carrée inverse
Pour calculer la racine carrée inverse d’un nombre a, on pourrait choisir d’inverser le nombre a (en payant le coût d’une division) et ensuite d’appliquer la méthode ci-dessus pour en trouver sa racine carrée (en payant à nouveau le coût d’une division à chaque itération). Mais on peut faire beaucoup mieux, en essayant de trouver directement la racine carrée inverse par la méthode de Newton.
Dans ce cas, cela reviens à chercher x solution de f(x)=0 avec
Si on calcule sa dérivée, on trouve
A première vue, tout cela ne semble pas très favorable, encore plein de divisions ! Mais regardons ce que devient l’itération, qui est je le rappelle définie par
Je vous laisse faire le calcul, on trouve
qui peut se récrire
Et là il se passe un truc tout à fait sympathique : il n’y a plus de divisions dans l’itération !
On voit qu’appliquer la méthode de Newton pour trouver directement la racine carrée inverse est en fait plus simple et facile que de passer par l’inverse et par la racine carrée ! L’algorithme est super simple !
Voici une méthode fort sympathique, mais on se retrouve avec le même problème que précédemment : comment partir du meilleur endroit possible ? Là, j’ai décidé de partir de 1/a, ce qui n’est pas forcément terrible, et qui en plus nous oblige à faire une division. Et c’est là que le génie de la méthode rapide intervient !
Le secret de la racine carrée inverse rapide
Regardez à nouveau l’algorithme de la racine carrée inverse rapide :
Peut-être que la logique du code vous semble plus claire. Observez les deux dernières lignes, ce sont exactement des itérations de la méthode de Newton, avec la formule qu’on vient de trouver. La seconde itération est commentée, car considérée comme superflue.
Et les 3 lignes qui sont au-dessus, c’est finalement “simplement” un moyen (tordu) de trouver un guess initial aussi bon que possible. Et celui-ci est tellement bon que derrière, une seule itération de la méthode de Newton suffit à donner une solution considérée comme largement suffisante (en fait : bonne à environ 1% près), c’est pourquoi l’auteur du code a choisi de commenter la seconde itération, inutile pour son application.
Nous arrivons à la fin de la première étape, et nous avons réduit le mystère de la racine carrée inverse rapide à un ingrédient : le choix d’un guess initial performant pour la méthode de Newton appliquée directement à la racine carrée inverse. Et dans le prochain article, on verra quelle est la diablerie qui se cache derrière cette initialisation, et pourquoi elle est si efficace.
(D’ici là, n’hésitez pas à aller voir le code sur GitHub)
Le temps béni où les programmeurs étaient d'autant plus astucieux que les ordinateurs étaient lents !
Bonjour
Je n’ai pas eu le temps de lire le post précédent sur l’IA. Comment le retrouver? C’était passionnant! Merci 🙏