Game developers didn’t have it easy in the 1990s. Because they had extremely limited computing power, they had to write their code as efficiently as possible. Take the first-person shooter Quake III Arena, usually called Quake 3, for example: players were navigating a three-dimensional world, so programmers had to find the smartest ways to handle 3D graphics and associated calculations.
Quake 3 was released in 1999 and is considered one of the best computer games of its time. This had a lasting impact on the industry. This legacy wasn’t so much due to the story, but rather the fact that Quake 3 was one of the first multiplayer first-person shooters. Players could connect their computers via network cables or the Internet to compete in real time.
The game code also left a mark. It included an extremely efficient algorithm that still amazes experts and arouses the curiosity of scientists.
On supporting science journalism
If you enjoy this article, please consider supporting our award-winning journalism by subscribe. By purchasing a subscription, you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.
A strange code
To mathematically determine the orientations of objects, characters, or other players in three-dimensional space, you create a vector, which is essentially an arrow that indicates direction. To compare vectors, they need to be normalized to the same length, so you need to scale them accordingly. And that’s where a tricky calculation comes in: the inverse square root, which is one divided by the square root of a number.
If I asked you to calculate the inverse square root of 26 without a calculator, you’d probably be stuck for a while – and honestly, so would I. In the 1990s, computers faced the same challenge. Even if they could analyze the numbers, the process required a lot of processing power, which could mean the calculation took a long time. One problem was the square root itself; another was division. That’s why Quake 3 programmers looked for a better way to find this inverse square root. And in fact, their source code revealed an ingenious solution.
What’s fascinating is that the developers never announced their trick. If Quake 3’s source code hadn’t become open source, their method might have remained hidden forever. But as soon as it was released, curious enthusiasts took notice. When they discovered the code snippet for calculating the inverse square root, they were baffled: it was difficult to follow, and the developer comments that came with it weren’t particularly helpful. But little by little, people understood how the code worked.
There is today many tutorials which guide you step by step through the program code. These walkthroughs exploit special features of the C programming language. For example, numbers are stored in computer locations called memory addresses, which are then manipulated. This is a clever way to avoid computationally intensive operations like division. “Think of it like putting the wrong label on something in the store and it convinces the employee, but here it’s C, we’re fools,” explained computer scientist Daniel Harrington of the University of Toronto in a presentation.
From a mathematical point of view, the code is easily explained. To determine the inverse square root, you must first guess the solution (which is usually incorrect) and then refine that guess through a defined procedure. In this way, we gradually arrive at better solutions.
None of this is revolutionary or new. What’s impressive, however, is that it typically takes four to five iterations of the process before the result is close enough to an actual solution. This process requires a lot of computing power. In Quake 3, the seed, i.e. the estimated number used in the first step of the process, has been chosen so intelligently that only one optimization step is necessary.
Looking for a magic number
The optimization steps correspond using the so-called Newton-Raphson methodwhich approximates the values at which a function produces an output of 0, or the root of functions, over many iterations. This may seem counterintuitive at first, since we want to calculate the inverse square root and not just any zero. But programmers employ a trick: they define the function to be approximated as the difference between the initial estimated value and the actual result. Thanks to the Newton-Raphson method, the error gradually becomes reduced, making it possible to get ever closer to the exact solution.
To think about it, imagine that you want to calculate the inverse square root of 2.5. The algorithm starts with a certain assumption: let’s say 3.1. To determine the difference from the actual solution, you square the initial value and divide one by the result. If 3.1 were really the inverse square root of 2.5, then 1 divided by 3.1 squared would be 2.5. The actual result is 0.1. The difference is therefore 2.4.
The Newton-Raphson method reduces this gap with each iteration to gradually get closer to the exact value. Generally, four to five of these steps are necessary to achieve a reliable result. Still, Quake 3 drastically reduced iterations.
The key lies in how the starting value of Newton’s steps is calculated. The method’s algorithm essentially works in three steps:
-
Take the given number whose inverse square root is to be calculated and convert it to a corresponding memory address (a location in the computer’s stored data).
-
This value is divided by two and subtracted from the hexadecimal value 0x5f3759df. This is the starting value of Newton’s method.
-
Next, perform a Newton step.
Particularly mysterious is the enigmatic string 0x5f3759df, which has since gone down in computing history as the “magic number.” This is why only one iteration is required to obtain an approximate inverse square root solution that produces an error of no more than 0.175 percent.
As soon as the program’s code was made available as open source, experts wondered about the origin of this magic number. In a technical article published in 2003, computer scientist Chris Lomont wrote: “Where does this value come from and why does the code work?”
The hexadecimal number 0x5f3759df corresponds to 1,597,463,007 in decimal notation. By breaking down the different steps of the program code, Lomont realized that he could obtain 1,597,463,007 through some calculations. To simplify this calculation, here is a way of representing the calculation involved:
Values 3⁄2223 and 127 come from the conversion of numerical representations in C. But the origin of 0.0450465 is less obvious.
Lomont studied mathematically which value gives an optimal result for different inputs. In other words: which starting value best approximates the inverse square root and should therefore lead to the smallest error? It arrived at a value of 1,597,465,647, or approximately:
This matches the values found in the Quake 3 source code. The result is quite close to the values found here.
When Lomont compared his results with those of the original, he was surprised. In two steps of the Newton-Raphson method, its calculated constant actually worked better: the maximum possible error was smaller than with the original code value. “And yet, surprisingly, after one Newton iteration, the maximum relative error is higher,” Lomont writes. “Which again begs the question: how was the constant in the original code derived?”
In his calculation, the computer scientist only considered which number would theoretically give the best possible value, neglecting the number of Newton steps. In search of a better constant, Lomont repeated his calculation and optimized it to obtain the best possible solution for a single Newton step. It arrived at a value of 1,597,463,174, or approximately:
When he put this to a practical test, it actually performed slightly better than the magic number in Quake 3’s code.
Lomont noted in his paper that since both constants are approximations, either is a good option in practice. He added that he hoped to meet the original author of the constant to find out how he derived the magic number.
Online communities have embarked on a never-ending search for this mysterious person. Special effort has been devoted to this effort Rys Sommefeldt, computer scientistwho first contacted John Carmack, the lead developer of Quake 3. Carmack was unsure who coded this snippet and could only offer guesses.
Sommefeldt contacted some of the most prominent developers of the 1990s, who each suggested other possible authors without claiming authorship. It now appears that Greg Walsh, who worked for computer maker Ardent Computer in the late 1980s, introduced the magic number into the inverse square root algorithm. He then found his way into the Quake 3 algorithm via several other individuals. But exactly how the magic number was determined remains unclear to this day.
This is not a particularly satisfying conclusion. Nonetheless, the story of Quake 3’s code – or at least the part that revolves around the inverse square root – is extremely fascinating. It’s amazing how much effort and intelligence went into efficient software programming back then – a trend that is often overlooked today due to today’s computing power.
This article was originally published in spectrum of science and has been reproduced with permission.