- #QUAKE 3 INVERSE SQUARE ROOT SOFTWARE#
- #QUAKE 3 INVERSE SQUARE ROOT CODE#
- #QUAKE 3 INVERSE SQUARE ROOT FREE#
It uses floating point format hacking and Newtons Method to implement a very fast inverse. The magic number also corrects for even/odd exponents the paper mentions you can also find other magic numbers to use. In this video we examine the 'fast inverse square root' method developed for Quake 3 Arena. However, there are several magic numbers that could be used - this one happens to minimize the error in the mantissa. If you want the inverse square root, divide the exponent by -2 to flip the sign. This is where the magic number comes in - it does some cool corrections for this division, that I don't quite understand. When you shift the entire number, you divide the exponent by 2, as well as dividing the number (5.4) by 2 as well. Floating-point numbers like $5.4 \cdot 10^6$ store their exponent in a separate range of bits than "5.4". The great hack is how integers and floating-point numbers are stored. More rounds are possible (at an additional computational expense), but one round is all that's needed for the precision needed. The result is that we get an initial guess that is really close to the real inverse square root! We can then do a single round of Newton's method to refine the guess.
#QUAKE 3 INVERSE SQUARE ROOT FREE#
As always, feel free to comment if you have a better explanation of what's happening. The paper has more details and explanation, I didn't catch all of it the first time around. This does a few things: it preserves the mantissa (the non-exponent part, aka 5 in: $5 \cdot 10^6$), handles odd-even exponents, shifting bits from the exponent into the mantissa, and all sorts of funky stuff. And lastly, to negate the exponent, we subtract from the magic number 0x5f3759df. It then shifts the bits by one, which means the exponent bits are divided by 2 (when we eventually turn the bits back into a float).
#QUAKE 3 INVERSE SQUARE ROOT CODE#
So, the code converts the floating-point number into an integer. A bizzare piece of code from quake 3 shows up on usenet with a magic constant that calculates the inverse. And if you want to get a negative number, instead of multiplying by -1 (multiplications are expensive), just subtract the number from "0" (subtractions are cheap). I love the story of the fast inverse square root. Right-shifting by one position is the same as dividing by two ( you can try this for any power of 2, but it will truncate the remainder).
Floating-point numbers are stored by computers in mantissa-exponent form, so it's possible to extract and divide the exponent!īut instead of explicitly doing division (expensive for the CPU), the code uses another clever hack: it shifts bits. So, how can we get the exponent of a number without other expensive operations? Floats are stored in mantissa-exponent form float y 1 / sqrt (x) But then again this functionality has already been figured out and can. The easy way to calculate the inverse of a square root being. When they did it was discovered was an algorithm that was so ingenious and all it did was calculate the inverse of a square root.
#QUAKE 3 INVERSE SQUARE ROOT SOFTWARE#
Now, if you want to find the regular square root, you'd just divide the exponent by 2:Īnd if you want the inverse square root, divide the exponent by -2 to flip the sign: In 2005 ID software open source the game Quake 3 Arena. Let's say you have a number in exponent form or scientific notation: An article and research paper describe a fast, seemingly magical way to compute the inverse square root ($1/\sqrt$?
0 kommentar(er)
