# Fast Inverse Square Root

Standard

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.

## One thought on “Fast Inverse Square Root”

1. dmaugis

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…