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.

Advertisements

One thought on “Fast Inverse Square Root

  1. 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…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s