November 01, 2011

Fast Inverse Square Root

So let's say you need to calculate  x-½ for what ever reason and you so happen to be working with 32-bit floating point numbers; well, apparently there is a little trick to calculate this value without resorting to a Taylor Series or intensive multiplication and division.

Take yourself back to 1990 working on Quake III Arena, when floating point calculation speed lagged behind integer calculations.  While this may not make sense to non-computer savvy people, just know that video games rely heavily on floating point calculations (which are numbers with decimal points to put it simply).

Another thing to note is that graphic intensive video games usually need to find the unit vector of various vectors to determine other things such as lighting, shading, directions, and reflections.

And how is the unit vector calculated?  BY INVERSE SQUARE ROOTS, DUH.

So how did the clever team working on Quake make a super fast function to calculate this number?  Magic:

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;

That is the original code with comments.  If you'd like to find out how it works exactly, check it out at:


Post a Comment