float Q_rsqrt( float number )
{
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = * ( long * ) &y; // evil floating point bit level hacking
i = 0x5f3759df - ( i >> 1 ); // what the fuck?
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
// y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed
return y;
}Why care
The cryptic function we see was used to calculate the reverse of square root, namely , but why care?
It turns out that if we want to implement physics or lighting in your game engine, it helps when the vector you’re calculated with are normalized to have length 1. The length of the vector can be calculated using Pythagorean theorem (in 3D of course), and thus each component will be , you might see where this is going :).
However, even though calculating exponent on computer is easy, doing division is slow and expensive. In a performance-critical scenario such as gaming, this “evil” function can dramatically improve performance (in that particular era).
Aside: Normal vectors are unit vectors aligned perpendicularly to a surface, defining its direction. They are commonly used for lighting, collisions, and other operations involving surfaces. Most of the time we only care about the direction of the light or physics and bringing in magnitude may even bring in some weird bugs, so a normalized vector is all we need. It also helps to separate the direction from the magnitude of your vector. For example, you can keep the speed of a character constant, even when they travel in weird diagonal directions.
But How
It mostly involves Binary calculation, Newton’s method, a few math tricks and Floating Point Representation, an additional blog concerning IEEE 754 can be found here.
Detailed visual proof can be found Here.
What Now
The first time I saw this algorithm, I was thrilled and immediately compare it with y = 1 / sqrt(x). But it disappointed me, by a lot. This magic function is now 10x slower!!!
Modern compiler, “No one knows optimization better than me”.
It is still a good starting point to learn IEEE 754 though.
Aside: In a recent Lex Fridman podcast with Carmack, he actually says that he didn’t invent this algorithm, this piece of code was found in the codebase but somehow everyone credits this function to him. He is now an VR in Meta.