Understanding = Quake=E2=80=99s Fast Inverse Square Root

BetterExplained
Understanding beyond your = textbook.=20

Understanding Quake=E2=80=99s Fast Inverse = Square Root

An article and=20 research=20 paper recently described an astonishingly fast, = seemingly=20 magical way to compute the inverse square root (1/sqrt(x)) = in the=20 game Quake.

I=E2=80=99m no expert in 3D graphics, but I can see how = square roots are=20 useful. The Pythagorean theorem computes distances, and can = help=20 normalize vectors (normalizing, by the way, is often just a = fancy=20 term for division). Games like Quake probably perform these=20 calculations zillions (yes, zillions) of times a second, so = speeding=20 up this critical path is important for performance. And by = the way,=20 exponentiation and division are really, really expensive for = the=20 CPU.

Given these conditions, here=E2=80=99s the function used = to compute=20 1/sqrt(x) inside Quake:


float InvSqrt(float x){
   float xhalf =3D 0.5f * x;
   int i =3D *(int*)&x; // store floating-point bits in integer
   i =3D 0x5f3759d5 - (i >> 1); // initial guess for Newton's =
method
   x =3D *(float*)&i; // convert new bits into float
   x =3D x*(1.5f - xhalf*x*x); // One round of Newton's method
   return x;
}

Somehow, this code computes 1/sqrt(x) via multiplication = and=20 bit-shift operations. No division or exponents are required! = Wow!

Summary as I understand it: This is a = great hack=20 that picks an awesome initial value for Newton=E2=80=99s = approximation=20 method. The function takes the inverse root by negating and = halving=20 the exponent of a floating-point number written in = scientific=20 notation. It uses a additional transformations to correct = for errors=20 and tada, you have your inverse square root.

Newton=E2=80=99s Method of Approximation

Newton=E2=80=99s method can be used to find approximate = roots of any=20 function. You can keep iterating the method to get closer = and closer=20 to the root, but this function only uses 1 step! = Here=E2=80=99s a=20 crash-course on Newton=E2=80=99s method (it was new to = me):

Let=E2=80=99s say you have a function f(x) and you want = to find its root.=20 Let=E2=80=99s call your original guess =E2=80=9Cg=E2=80=9D. = Newton=E2=80=99s method gives you a way=20 to get a new, better guess:

You can keep repeating this process (plugging in your new = guess=20 into the formula) and get closer approximations for your = root.=20 Eventually you have a =E2=80=9Cgnew=E2=80=9D that makes = f(gnew) really, really close=20 to zero =E2=80=94 it=E2=80=99s a root! (Or close enough for = government work, as they=20 say).

In our case, we want the inverse square function. = Let=E2=80=99s say we=20 have a number =E2=80=9Ci=E2=80=9D (that=E2=80=99s all we = start with, right?) and want to=20 find the inverse square root: 1/sqrt(i). If we make a guess = =E2=80=9Cx=E2=80=9D as=20 the inverse root, the error between our original number and = our=20 guess =E2=80=9Cx=E2=80=9D is:

$3D"\displaystyle{error(x)$

This is because x is roughly 1/sqrt(i). If we square x we = get=20 =E2=80=9C1/i=E2=80=9D, and if we take the inverse we should = get something close to=20 =E2=80=9Ci=E2=80=9D. If we subtract these two values, we can = find our error.

Clearly, we want to make our error as small as possible. = That=20 means finding the =E2=80=9Cx=E2=80=9D that makes error(x) = =3D 0, which is the same as=20 finding the root of the error equation. If we plug error(x) = into=20 Newton=E2=80=99s approximation formula:

and take the proper derivatives:

$3D"\displaystyle{error(g)=3D$

$3D"\displaystyle{error'(g)=3D$

we can plug them in to get the formula for a better = guess:

$3D"\displaystyle{newguess$

Which is exactly the equation you see in the code above,=20 remembering that x is our new guess (g) and = =E2=80=9Cxhalf=E2=80=9D is half of the=20 original value (0.5 * i):

x =3D x*(1.5f - xhalf*x*x);

With this formula, we can start with a guess = =E2=80=9Cg=E2=80=9D and repeat the=20 formula to get better guesses. Try this demo of using = multiple=20 iterations to find the inverse square. If you plug in = different=20 initial guesses (.2, .4, .8) you can see how quickly the = guesses=20 converge to the real answer.

So my friends, the question becomes: =E2=80=9CHow can we = make a good=20 initial guess?=E2=80=9D

Making a Good Guess

So, what=E2=80=99s a good guess for the inverse square = root? It=E2=80=99s a bit=20 of a trick question =E2=80=94 our best guess for the inverse = square root is=20 the inverse square root itself!

Ok hotshot, you ask, how do we actually get=20 1/sqrt(x)?

This is where the magic kicks in. Let=E2=80=99s say you = have a number in=20 exponent form or scientific notation:

10^6 =3D 1 million

Now, if you want to find the regular square root, = you=E2=80=99d just=20 divide the exponent by 2:

And if you want the inverse square root, = divide=20 the exponent by -2 to flip the sign:

So, how can we get the exponent of a number without other = expensive operations?

Floats are stored in mantissa-exponent form

Well, we=E2=80=99re in luck. Floating-point numbers are = stored by=20 computers in mantissa-exponent form, so it=E2=80=99s = possible to extract and=20 divide the exponent!

But instead of explicitly doing division (expensive for = the CPU), the code uses another clever hack: = it shifts=20 bits. Right-shifting by one position is the same as dividing = by two=20 (you=20 can try this for any power of 2, but it will truncate = the=20 remainder). And if you want to get a negative number, = instead of=20 multiplying by -1 (multiplications are expensive), just = subtract the=20 number from =E2=80=9C0=E2=80=B3 (subtractions are = cheap).

So, the code converts the floating-point number into an = integer.=20 It then shifts the bits by one, which means the exponent = bits are=20 divided by 2 (when we eventually turn the bits back into a = float).=20 And lastly, to negate the exponent, we subtract from the = magic=20 number 0=C3=975f3759d5. This does a few things: it = preservers the=20 mantissa (the non-exponent part, aka 5 in 5*10^6), handles = odd-even=20 exponents, shifting bits from the exponent into the = mantissa, and all sorts of funky stuff. The paper has more = details=20 and explanation, I didn=E2=80=99t catch all of it the first = time around. As=20 always, feel free to comment if you have a better = explanation of=20 what=E2=80=99s happening.

The result is that we get an initial guess that is really = close=20 to the real inverse square root! We can then do a single = round of=20 Newton=E2=80=99s method to refine the guess. More rounds are = possible (at an=20 additional computational expense), but one round is all = that=E2=80=99s=20 needed for the precision needed.

So, why the magic number?

The great hack is how integers and floating-point numbers = are=20 stored. Floating-point numbers like =E2=80=9C5.4 * = 10^6=E2=80=B3 store their=20 exponent in a separate range of bits than = =E2=80=9C5.4=E2=80=B3. When you shift the=20 entire number, you divide the exponent by 2, as well as = dividing the=20 number (5.4) by 2 as well. This is where the magic number = comes in =E2=80=94=20 it does some cool corrections for this division, that I = don=E2=80=99t quite=20 understand. However, there are several magic numbers that = could be=20 used =E2=80=94 this one happens to minimize the error in the = mantissa.

The magic number also corrects for even/odd exponents; the=20 paper mentions you can also find other magic numbers to = use.

Resources

There=E2=80=99s further discussion on reddit (user = pb_zeppelin) and=20 slashdot:

http://programm= ing.reddit.com/info/t9zb/comments=20
http://games.slashdot.org/article.pl?sid=3D06%2F12%2F01%2F184205=20 and my=20 comment

Posted February 6, 2007, under Programming
Tags: approximation, binary, bit, hack, newton, problem solving, programming, shift
Related Posts:=20

Debugging with GDB

Marketing Lessons from InstaCalc.com

Understanding the Pareto Principle (The 80/20 = Rule)

Vector Calculus: Understanding the = Gradient

Vector Calculus: Understanding Divergence =

Like = it? Share=20 on:

No Comments =C2=BB=20

No comments yet.

RSS feed for = comments on=20 this post. TrackBack URI

Have a question? Know an explanation that caused your own = a-ha=20 moment? Write about it here.