# Float inverse square root approximation

Code
``` 01: float invSquareRootFastest(float x) 02: { 03:   // access float with integer logic 04:   unsigned int *i = (unsigned int*) &x; 05:   // approximation with empirically found "magic number" 06:   *i = 0x5F375A86 - (*i>>1); 07:   return x; 08: } 09: 10: float invSquareRoot(float x) 11: { 12:   // for Newton iteration 13:   float xHalf = 0.5f*x; 14: 15:   // same as above 16:   unsigned int *i = (unsigned int*) &x; 17:   *i = 0x5F375A86 - (*i>>1); 18: 19:   // one Newton iteration, repeating further improves precision 20:   return x * (1.5f - xHalf*x*x); 21: } ``` bits.stephan-brumme.com

Explanation The inverse square root can be rewritten with an exponent: 1/√(x) → x
When x already is expressed with an exponent, say x → ab, then 1/√(x) → 1/√ ab  → a-b/2

TODO

Restrictions • designed for positive 32 bit floats
• approximation, average deviation of ≈ 5%
- for example: √144 = 12, but squareRoot(144) = 12.5, ≈ 4% off

help me to pay
my server bills

Performance • constant time, data independent

• 2.67 GHz Intel® Pentium™ D805, Microsoft Visual C++ 2005, highest level of optimization:
≈ 950 million numbers per second
≈ 3 cycles per number

• 2.67 GHz Intel® Pentium™ D805, GCC 3.4.5 (MinGW), highest level of optimization:
≈ ??? million numbers per second
≈ ? cycles per number CPU cycles
(full optimization,
lower values are better)