https://attackofthefanboy.com/articles/the-quake-iii-algorithm-that-defies-math-explained/
I know next to nothing about programming and physics, but I do know this article intrigues me. I’m mostly interested in how the algorithm “allowed the game to function faster and more smoothly,” and why it’s “seemingly mathematically impossible.”
In: 119
First it gets an approximation of the value and refines this approximation using a single iteration of Newton’s method.
Newton’s method is not as interesting here because it is used in many other situations as well. One thing that is important here is that our initial approximation (that the method receives) must not be totally off because otherwise our result gets worse with each iteration and quickly blows up. For example we want to calculate inverse square root of 123, if we told the method that our initial guess was 1 (which is always a better guess than the number itself), the first iteration of the method would give us back the number -60 which is a negative number and not acceptable for a square root. After the second iteration the value becomes 13283910 and there is no way to recover from that.
The interesting part is the initial approximation. So how could we estimate the inverse square root of a number like 123? Well, the number can equivalently be represented as 1.23 * 10^2. We ignore the 1.23 part and focus on the 10^2 part. We can apply the inverse square root directly on this part. (10^2)^(-0.5) is the same as 10^(2*-0.5) which is 10^(-1). So we multiply the exponent by -0.5 (or divide by -2) to get our estimate. In this case, the result would be 10^-1 = 0.1 which would be our initial approximation. Using Newton’s method then turns it into 0.0885 which is not too far from the expected value of 0.0902. If we run a second iteration of Newton’s method we end up with 0.901. The important part is that getting the (inverse) square root of a number like 100 or 10000 is extremely simple whereas dealing with a number like 1.23 is a huge challenge.
So we can get a decent approximation just by looking at the exponent. And this exponent is essentially the log10 of the number. If you have the number 123 then the log10 is 2.09 where the 2 corresponds to the 10^2 part from before (and the 0.09 corresponds to 1.23 because 10^0.09 is 1.23). We already know what to do with the log10. We divide it by -2 and use that as our new exponent. I.e. -2.09/2 is our new exponent which means the number is 10^(-1.045) and that is exactly the inverse square root.
Having the log of the number basically tells you how many digits (minus 1) it has. Now, the computer works in binary but the idea is the same. The first step is to calculate the log2 of a floating point number (represented as exponent E and mantissa M) and it happens that log2(x) = 1/2^23 * (E*2^23 + M) – 126.9549534 is a good approximation. How they arrived at that approximation is not that important right now; it’s just a mixture of a Taylor series of log(x+1) and some fine tuning in the interesting region of x values.
The important part is that the formula above incorporates both exponent and mantissa (whereas our initial approach only uses the exponent) and it uses them in a very inexpensive way. It is just addition and subtraction and multiplication.
The (E*2^23 + M) is x interpreted as an integer, which we call i. So log2(x) = 1/2^23 * i – 126.9549534. To get the inverse square root in log space, we divide by -2 and get -log2(x)/2 = 126.9549534/2 – 1/2^23 * (i/2).
The last obstacle is to go back from the log2 representation into the (exponent, mantissa) representation. It’s basically just some algebra and they arrive at (exponent, mantissa) = 3/2 * 126.9549534*2^23 – i/2 where the right hand side is calculated as an integer and then interpreted as a floating point number.
Latest Answers