Game developers didn’t have it easy in the 1990s. Since they had extremely limited computing power, they had to write their code as efficiently as possible. For example, consider the first-person shooter Quake III Arena, commonly known as Quake 3: players navigated a three-dimensional world, so programmers had to find the cleverest ways to handle 3D graphics and related 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 was not because of the story, but because Quake 3 was one of the first multiplayer first-person shooters. Players can connect their computers via network cable or the Internet to compete in real time.
The game’s code also left an impression. It involves an extremely efficient algorithm that still amazes experts and arouses curiosity among scientists.
On supporting science journalism
If you enjoyed this article, consider supporting our award-winning journalism Subscribing By purchasing a subscription, you are helping ensure a future of impactful stories about the discoveries and ideas shaping our world today.
a strange code
To mathematically detect the orientations of objects, characters, or other players in three-dimensional space, you create a vector, which is essentially an arrow that shows direction. To compare vectors, they need to be normalized to the same length, so you have to scale them accordingly. And this is where a tricky calculation comes in: the inverse square root, which is dividing 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. Computers also had to face the same challenge in the 1990s. Although they can crunch numbers, the process requires a lot of processing power – which can mean calculations can take a lot of time. One problem was the square root itself; The second was partition. That’s why Quake 3 programmers searched for a better way to find this inverse square root. And in fact, their source code A unique solution emerged.
Interestingly, the developers never advertised their trick. If the source code of Quake 3 had not been open source, their method would have remained hidden forever. But once it was released, curious enthusiasts took notice. When they discovered the code snippet for calculating the inverse square root, they were astonished – it was difficult to follow, and the developers’ comments were not particularly helpful. But gradually people came to know how the code worked.
are today many tutorials Which guides you step-by-step through the program code. These walkthroughs take advantage of 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 a mistag on something in a store and convincing the employee, but we’re the fools here.” Daniel Harrington, a computer scientist at the University of Toronto, explained In a presentation.
From a mathematical point of view, the code can be easily explained. To determine the inverse square root, you first make a guess at the solution (which is usually wrong) and then refine that guess through a prescribed procedure. In this way it gradually reaches a better solution.
None of this is unprecedented or new. What is impressive, however, is that it usually requires four to five iterations of the process before the result is close enough to the actual solution. This process requires a lot of computing power. In Quake 3, the initial values – that is, the estimated numbers used in the first step of the process – were so cleverly chosen that only one optimization step is necessary.
looking for a magic number
The optimization steps are consistent For the so-called Newton-Raphson methodWhich estimates the values at which a function produces an output of 0 or the root of the function over a number of iterations. This may seem counterintuitive at first, because one wants to calculate the inverse square root, not just zero. But programmers take a trick: They define the function to be estimated as the difference between the initial guess value and the actual result. Through Newton–Raphson’s method, the error becomes progressively smaller, getting one closer to the exact solution.
To consider this, imagine you want to calculate the inverse square root of 2.5. The algorithm starts from a fixed estimate: Suppose 3.1. To determine the difference from the actual solution, you square the starting value and divide one by the result. If 3.1 were actually the inverse square root of 2.5, then dividing 1 by 3.1 squared would yield 2.5. The actual result is 0.1. Hence the difference is 2.4.
The Newton-Raphson method reduces this difference at each iteration so that you gradually get closer to the exact value. Four to five such steps are usually required to reach a reliable result. Yet Quake 3 reduced iterations significantly.
The main thing is how the starting value of Newton’s steps is calculated. The algorithm of the method essentially operates in three steps:
-
Take the given number whose inverse square root is to be calculated and convert it to the corresponding memory address (a location in the computer’s stored data).
-
This value is halved and subtracted from the hexadecimal value 0x5f3759df. This is the initial value of Newton’s method.
-
Next, execute the Newton step.
The secret string 0x5f3759df is particularly mysterious, which has since gone down in the history of computer science as a “magic number”. This is why only one iteration is necessary to obtain an approximate solution for the inverse square root which produces a maximum error of 0.175 percent.
As soon as the program code became available as open source, experts puzzled over the origin of that magic number. In a technical paper 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 program code into individual steps, Lomont realized that he could get to 1,597,463,007 through a few calculations. To simplify this math, here’s a way to represent the calculations involved:
Value 3⁄2223 And 127 comes from converting the number representation to C. But the origins of 0.0450465 are less clear.
Lomont investigated mathematically which value gives the optimal result for different inputs. In other words: which initial value best approximates the inverse square root and therefore should lead to the smallest error? He arrived at a value of 1,597,465,647, which is approximately:
This matches the values found in the Quake 3 source code. The result is very close to the values found there.
When Lomont compared his results with the original results, he was surprised. In two stages of the Newton–Raphson method, their calculated constant actually worked better: the maximum possible error was smaller than the value in the original code. Lomont writes, “Yet surprisingly, after one Newton iteration, it has a maximum relative error.” “Which again raises the question: how were the original code constants obtained?”
In his calculations, the computer scientist only considered what number would theoretically provide the best possible value, ignoring the number of Newton steps. In search of better constants, Lamont repeated his calculations and optimized them for the best possible solution for a single Newton phase. He arrived at a value of 1,597,463,174, which is approximately:
When they put this result to a practical test, it actually yielded slightly better results than the magic number in the Quake 3 code.
Lomont noted in his paper that since both constants are approximations, in practice either one is a good choice. He further said that he hoped to meet the original author of the constant to learn how he arrived at the magic number.
Online communities began a sustained search for this mysterious individual. was specifically dedicated to this effort Computer scientist Rhys SomefeltWho first contacted John Carmack, the lead developer of Quake 3. Carmack was unsure who coded this snippet and could only offer guesses, however.
Sommefelt contacted some of the most prominent developers of the 1990s, each of whom suggested other possible authors without claiming authorship for themselves. It now appears that Greg Walsh, who worked for computer manufacturer Ardent Computer in the late 1980s, introduced the magic number into the inverse square root algorithm. It then found its way into the Quake 3 algorithm through several other individuals. But how exactly the magic number was determined remains unclear to this day.
This is not a particularly satisfying conclusion. Still, the story of the Quake 3 code – or at least the part that revolves around the inverse square root – is extremely interesting. It’s amazing how much effort and brainpower went into efficient software programming at that time – a trend that is often overlooked today due to current computing power.
This article was originally published in spectrum der wissenschaft And was reproduced with permission.
