I remembered that I hit a bottle neck while doing the project for my thesis. After gathering detection windows of pedestrians, I needed to apply Mean Shift clustering in order to have final detection windows.

However, one of the line of codes that ended up as bottleneck was pow( x, -0.5 ). Googling around, I managed to find a piece of code from Quake III Arena (yeah, Quake III Arena, but the code wasn’t from Carmack though).

It’s fast inverse square root approximation. Sure it’s not accurate, but I was doing Mean-shift anyway, as long as the results converge, then it’s good.

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;
}

You can read more about fast inverse square root approximation here: http://en.wikipedia.org/wiki/Fast_inverse_square_root

So next time, if you have some bottleneck with inverse square root, and precision is not a big issue, you might want to consider this piece of code.

### Like this:

Like Loading...

yes, the code is also in one of the “Graphic Gems” volume, together with plenty of tricks to speedup tan, atan, sin etc…. Id Software was using quite a lot of ficed point calculation at a time…