## Fast inverse of square root

Moderator: Benj

Mantas
Posts: 221
Joined: Tue May 15, 2012 10:32 pm
Location: Klaipeda, Lithuania - North sea, UK
Contact:

### Fast inverse of square root

Hello MM,

As you know sometimes microcontrollers struggle with computation intensive functions, and you want to optimize the code to make life easier for them. So you probably remember the famous hack from Quake ||| to compute the inverse square root of x, if not, here is a remainder how it looks:

Code: Select all

``````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 f***?
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;
}``````
I was doing some really complex functions for quaternion calculations and decided to use the famous hack to improve on speed. But this function leads to max error of about 1.75233867·10−3 and average of 1.24792411·10−6.
I did a little bit of googling and found that one crazy kid found better coefficients for the same hack, and it looks like this:

Code: Select all

``````float inv_sqrt(float x)
{ union { float f; uint32 u; } y = {x};
y.u = 0x5F1FFFF9ul - (y.u >> 1);
return 0.703952253f * y.f * (2.38924456f - x * y.f * y.f);
}``````
This improves the error quite a lot leading to max of 6.50196699·10−4 and an average of 2.00010826·10−7. So my offer is to incorporate this cool function into FC library just in case someone needs it

Best regards,
Mantas

Edited out swear word as people under 18 could be reading forums..Martin
Science is my true religion.

Mantas
Posts: 221
Joined: Tue May 15, 2012 10:32 pm
Location: Klaipeda, Lithuania - North sea, UK
Contact:

### Re: Fast inverse of square root

For the time being here is a macro if someone needs to use it in the FC before we have it in the library. I have attached a sample program if anyone needs to test it. You can clearly see how accurate the answer is.

Best regards,
Mantas
Attachments
invsqrt.fcf_arm
Sample program