One of my favorite hobbies is called recreational mathematics. This is the kind of revelation that I can only offer in the pages of this magazine and other select locations, feeling confident and hopeful that there is a more receptive public here than, say, at a Christmas dinner conversation or at the pub.
This is why I found fascinating the recently discovered aperiodic monotile solving the so-called Einstein’s problem (and Rob Pike found it fascinating too). I learned about this quite inefficient formula returning the nth prime. I marveled at Tupper’s self-referential formula that draws itself when plotted on a graph. I discovered a curious integral whose result is equal to the inverse of e. I delighted in the infinite curiosities around Fibonacci numbers. I watched in awe Arthur Benjamin correctly guessing dates and squaring five-digit numbers with fishes and cookies. And so on and so forth.
This is also the reason why I subscribed to various channels on YouTube with such content: Math with Janine, Veritasium, Michael Penn, Numberphile, Stand-up Maths, Jeffrey Caplan, Mathemaniac, Quanta Magazine, The Math Sorcerer, the greatly missed PBS Infinite Series, the outstanding Mathologer, the even more incredible 3Blue1Brown, and Nemean.
Nemean features only four videos at the time of this writing, but with excellent content and production. Among those videos, we find the subject of this month’s Vidéothèque article, the explanation of the Fast Inverse Square Root algorithm.
The original algorithm was discovered in the source code of Quake III Arena, released to the public in August 2005. (We’ve talked about id software and their coding prowess just two months ago.) It is used to normalize vectors used in 3D rendering, an operation repeated ad nauseam in real time as players navigate through the game. This operation is related to Pythagoras’ theorem, but the code features an embedded “magic” 0x5f3759df number in it. What is that constant for?
As a short summary of the movie, suffice to say that while additions and multiplications are fast to execute, square roots are not. Quite the opposite, actually, particularly in late 1990s hardware. The trick of this algorithm consists in working directly with floating-point number representations, bit shifts, and logarithms, to reach a “good enough” result; ideally with an error lower than 1%.
And lo and behold, this algorithm does the trick.
The video divides the explanations in three parts: “Evil bit hack,” “What the fuck,” and “Newton iteration.” Understanding how this all works together requires some math and computer science background: the IEEE 754 standard, memory address access tricks in C (to read a float as if it were an int and vice versa), logarithms, and Newton’s method.
A Wikipedia page provides even more information about this algorithm, which, to be honest, was not invented by Carmack or anyone else at id software (spoiler alert: it existed since the 1980s.) Nevertheless, this video provides an excellent introduction to the subject, and more importantly, a peek at the complexities of working with real numbers in a real computer (pun intended) in a context such as games, where speed and efficiency are as crucial for success as visual design.
The real problem surfaces when such optimizations are used in non performance-sensitive contexts, like line-of-business applications. As one of the commenters below the video said,
Id’s performance tuning was something that us programmers would nerd out about, and I’d often write my code to similar standards. Curious coworkers would sometimes encounter some of my “performance-tuned code” and be like “uhh, why did you do this like that?” I’d explain all about efficiencies and they’d just kind of roll their eyes and be like “okaaayy.”
Knowledge of these hacks is useful, but context is king. Decades later, the good old sqrt() function in <math.h> provides excellent performance in our multicore world; let us keep such hacks as historic curiosities, and let us make sure that our code is readable by all of our coworkers.
And please remember not to sprinkle your code with magic constants such as 0x5f3759df. Please.
Cover snapshot by the author.
