0x5F3759DF : le nombre magique qui a rendu la 3D possible

Quelque part dans le code source de Quake III Arena, le jeu de tir de 1999 qui a appris à toute une génération ce que valaient 125 images par seconde, il y a une fonction. Elle fait une vingtaine de lignes, calcule un bout de mathématiques parfaitement banal, et en plein milieu trône un commentaire devenu légendaire : // what the f***?. Même les programmeurs qui l'ont publiée n'étaient pas tout à fait sûrs de pourquoi ça marchait. Le tour de force qu'ils réussissaient — calculer un sur la racine carrée d'un nombre, plus vite que le matériel de l'époque ne savait le faire honnêtement — est l'un des plus beaux bidouillages de l'histoire du code. Et en son cœur, un seul nombre hexadécimal, presque magique : 0x5F3759DF.

Pourquoi un jeu passe sa vie à diviser par une racine carrée

La 3D, sous les explosions, c'est une quantité énorme de géométrie. Pour savoir comment une surface accroche la lumière, comment un mur réfléchit, si un ennemi est devant ou derrière vous, le moteur manipule en permanence des vecteurs normalisés — de petites flèches de longueur exactement un, pointant dans une direction. Transformer une flèche quelconque en flèche de longueur un revient à diviser chacune de ses composantes par sa longueur, et une longueur, c'est une racine carrée. Le moteur a donc besoin de 1 / √x, la racine carrée inverse, des millions de fois par seconde.

La façon honnête de calculer ça sur un processeur de 1999 était d'une lenteur brutale. Racines carrées et divisions comptaient parmi les opérations les plus coûteuses d'un processeur — le genre de chose qui, répétée des millions de fois par image, transformait votre tir nerveux en diaporama. La question des programmeurs n'était donc pas comment obtenir la réponse exacte, mais à quel point peut-on s'en approcher, vite, et assez bien pour que personne ne le remarque.

Le tour de bits qui ne devrait pas marcher

Voici le tour de passe-passe. Un nombre à virgule flottante — la façon dont les ordinateurs stockent les décimales — n'est qu'un motif de bits : un signe, un exposant et une fraction. L'idée géniale, c'est que cette disposition encode secrètement un logarithme. Les bits d'exposant correspondent en gros à la partie entière du log₂ de votre nombre, et les bits de fraction en approchent le reste.

Et la racine carrée inverse, dans le monde des logarithmes, devient presque triviale : faire 1/√x revient à multiplier le logarithme par −½. L'algorithme fait alors une chose qui semble totalement folle. Il prend le nombre flottant, réinterprète ses bits bruts comme un entier ordinaire (sans conversion, juste « lire la même mémoire comme si c'était un autre type »), puis calcule, grosso modo, magique − (i >> 1). Le décalage à droite divise la valeur par deux ; la soustraction à la constante magique inverse le signe et applique la correction. Relisez ces bits entiers comme un flottant et — stupéfaction — vous obtenez une excellente estimation de 1/√x. Une seule ligne de tripatouillage de bits, d'allure illégale, a remplacé une racine carrée et une division.

Ce qu'est vraiment 0x5F3759DF

Ce nombre magique n'a rien d'aléatoire, et ce n'est pas une coquille. C'est la constante qui fait tomber juste tout le tour de logarithme. Quand on divise par deux et qu'on inverse ces bits d'exposant, on introduit une petite erreur systématique, et 0x5F3759DF est réglé pour la garder aussi équilibrée — aussi faible dans le pire des cas — que possible. C'est, au sens propre, l'entier le mieux choisi de tout ce coin de l'imagerie de synthèse.

L'estimation qu'il produit est bonne, mais pas parfaite, alors le code se termine par un passage de la méthode de Newton — une technique vieille de plusieurs siècles pour affiner une approximation. Une seule itération reprend la réponse grossière et la raffine à environ 0,17 % de la vraie valeur. Largement assez précis pour éclairer un rocket-jump en deathmatch, et l'ensemble tournait à peu près quatre fois plus vite que le calcul direct. (Un second passage de Newton resserrerait encore l'erreur, mais pourquoi payer une précision que personne ne voit ?)

Le mystère de l'auteur

Pendant des années, la légende a attribué 0x5F3759DF à John Carmack, le célèbre programmeur en chef d'id Software. L'histoire était propre — codeur de génie, bidouille de génie — mais elle était fausse. Carmack a publié le code ; il n'a pas inventé le nombre.

Quand id a publié le code source de Quake III à la QuakeCon de 2005, l'énigme n'a fait que s'épaissir, et des programmeurs curieux se sont mis à fouiller. La piste, reconstituée en grande partie par une enquête de 2006, remonte, via le fabricant de puces Ardent Computer, jusqu'à un programmeur nommé Greg Walsh, qui a conçu la fameuse constante à la fin des années 1980. Walsh tenait l'idée sous-jacente du tripatouillage de bits du mathématicien Cleve Moler (le créateur de MATLAB), qui l'avait lui-même vue dans un article non publié de 1986 signé William Kahan et K. C. Ng à Berkeley — Kahan étant précisément l'homme qui a coécrit la norme régissant la manière dont les ordinateurs manipulent les nombres à virgule flottante. Ce bidouillage qui avait des airs d'heureux accident était en réalité l'intelligence distillée de quelques-uns des plus profonds esprits du calcul numérique de l'époque, transmise de main en main pendant plus d'une décennie avant de faire enfin voler une roquette.

La chute

La dernière pirouette est presque poétique. Quelques années après la publication du code, des mathématiciens se sont penchés sur la question pour chercher le nombre magique vraiment optimal — et ils en ont trouvé un légèrement meilleur, 0x5F375A86. La constante légendaire, celle gravée dans le folklore de la programmation, celle au commentaire ahuri juste à côté, n'a jamais tout à fait été le meilleur choix. Elle était simplement assez bonne, assez rapide, et livrée — ce qui, au fond, est exactement la façon dont on fait un jeu.