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

These ads
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
Performance Chart
CPU cycles
(full optimization,
lower values are better)

Download The full source code including a test program is available for download.
A precompiled Windows command-line executable (66 kB) is available as well.

References Quake3 source code
Chris Lomont, "Fast Inverse Square Root"

More Twiddled Bits
  1. Absolute value of a float
  2. Absolute value of an integer
  3. Approximative inverse of a float
  4. Bit manipulation basics
  5. Bit mask of lowest bit not set
  6. Count bits set in parallel a.k.a. Population Count
  7. Detects zero bytes inside a 32 bit integer
  8. Endianess
  9. Extend bit width
  10. Float inverse square root approximation
  11. Float square root approximation
  12. Is power of two
  13. Minimum / maximum of integers
  14. Parity
  15. Position of lowest bit set
  16. Round up to the next power of two
  17. Sign comparison
  18. Sign of a 32 bit integer
  19. Swap two values
Extra: Javascript bit manipulator

... or go to the index