The Best Approximation of All Time
This post is derivative
The what?
There comes a time in every computer-oriented blog where this post is made, rather than delaying the inevitable, I feel it is time to commit to writing and get it over with.
This post is about one of the best approximations of all time, the Fast Inverse Square Root. 
I’d like to go over why we need this first, since I rarely have encountered detailed backgrounds.
Normal Vectors
In computer graphics, normalised vectors ( magnitude of the vector is 1, or more formally ) are used a lot for lighting (luminence, shadows, reflections and more).
By a lot, I mean millions of times a second, as every angle of incidence and reflection is calculated using these vectors, .
Before I discuss why this is such a problem, I would first like to discuss how we get these vectors ( ).
Objects in computer graphics are polygons defined as a set of surfaces, which have 3D coordinates for each vertex (corner). Triangles are commonly used as they have three vertices, the minimum number required to define a flat plane.
Using the set of three points used to define the surface we can now try and find a surface normal.
We can consider as our reference point for the object, and define the order of the points (1,2,3) to be what we would see if we look face on and proceed anti-clockwise around the polygon. The anti-clockwise property is important and I shall explain later.
To further set up the problem, we now need to find the difference between our other vertices and the reference point as the vector from to where is 2 or 3. I am going to use the shorthand to resemble this vector.
It might be easier to show diagrammatically, before we make any further steps. The diagram below shows a triangle we are looking at that is facing us (surfaced side up).
From here it is relatively easy to get the normal! We have an oriented surface now defined by two vectors, so we can take the cross product ( ).
A cross product is an operation that exists only in three and seven dimensional spaces which allows us to multiply two vectors in such a way that a new vector is made which is orthogonal (at right angles) to both of the two generating vectors.
The benefit of the way we oriented our triangle is that the surface normal will be emerging from the side which has the top of the surface.
A diagram is provided to aid understanding on what we have just done:
To humour ourselves, although not the goal of this post, we can test for polygon visibility. We have , we can run a simple test to see if the polygon is facing us. If we draw a vector from the surface to the location of the observer and call it , we can take the dot product, and if , the surface is facing us.
Normalised Normals
As I mentioned at the beginning of this post, we are interested in normalised surface normals, which I named .
There is fortunately a method to calculate this, we take the Euclidean Norm (which is Pythagoras’ theorem in higher dimensions - try it, the proof is simple) and divide by it.
Where
so in one equation we can get our :
Let’s program it in our computer from the 1990s and give it a burl! Wait, why is everything so sluggish?
It turns out that floating point division and square roots are really slow for computers before efficient versions of those methods existed on-chip. Multiplication is fast, addition and subtraction are fast, but division and square roots are recursively defined and are very slow.
All of our problem used multiplication, subtraction and addition up until the point where we needed to normalise.
This begs the question, is there a way to rephrase it as problem of multiplication, so we can run this millions of times a second?
If we allow ourselves to imagine we have an algorithm that finds , then we can do . This is just multiplication which should be fast! All we need is the impossible algorithm that finds in a timely manner.
The good bit
John Carmack was the lead programmer of Wolfenstein 3D, Doom, Quake, Rage and Commander Keen, so it is fair to say he knows a lot about computer graphics. He was one of the pioneers of computer graphics in the 1990s, and he wrote that magical algorithm which performs a fast inverse square root.
What lies ahead is madness, so buckle up and don’t be worried if it makes no sense.
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;
}
Although we were probably most fixated on the humorous (original) comments, we have a lot of complicated ideas going on in one place, so let’s break it down and see if we can figure out how it works.
We have a function which takes a float number and returns a float. This is fine.
We start by defining some variables and a constant. We have a long integer i, two floats x2, y and a constant float threehalfs. This, also, is fine.
We then set x2 = number * 0.5F and y = number, if you are unfamiliar with C, we can define a float by putting an F at the end of a number. Again this is fine.
Suddenly it’s anything but fine. We are presented with:
i = * ( long * ) &y; // evil floating point bit level hacking
This is a little nasty, it interprets the 32 bit float as an integer. 32 bit floats are structured as its most significant bit resembling the sign, the next eight resembling the exponent and the remaining 23 the ‘mantissa’.
We know we are always passing positive values into Q_rsqrt by nature of this problem, so the sign bit will be zero!
All we have to worry about is the exponent and mantissa, which I will interpret as integers and label them
and
.
32 bit floats use the mantissa and exponent (ignoring sign) to define numbers as follows:
The 127 is the exponent bias. The exponent is stored as an unsigned 8 bit number, so 127 is taken off it to allow negative powers of two as well as positive ones. Keep an eye on it, it comes back later.
If we directly interpret the float as an integer, we have:
Now we have the background covered, let’s dive into the hack behind this line of code.
We begin by taking the logarithm of .
If we squint hard enough (and boy do you have to squint), it looks similar the integer representation although out by a constant and a multiplicative coefficient!
This is due to the fact we can approximate for .
We can do a little better than that. The line touches the curve at both ends and sits under it everywhere else, so it always comes up short. Lifting it by a small constant splits the difference, so the error is spread evenly above and below the curve:
With we’re back to the plain approximation, and the that makes the worst error as small as possible is half the widest gap, about . Hang on to : it is most of the secret behind the magic number.
Using that in our logarithm, we are left with:
Now look at the integer again. Dividing by gives , which is exactly the shape above. So:
Or, turning it round:
Interpreting a float as an int is a poor-man’s logarithm with base two! It is scaled by and shifted by , but it is a logarithm.
Hummus and Magnets walks through this too, and it’s well worth a read.
Where the magic number comes from
i = 0x5f3759df - ( i >> 1 ); // what the fuck?
Call the number we were given and the answer we want . Take the logarithm of both sides:
By Jove! The square root has become a halving, and the reciprocal has become a minus sign. Both of those are cheap.
Now swap each logarithm for the poor-man’s version. Writing and for the integer readings of and :
Multiply through by and gather the constants on one side:
That is the line of code, term for term. ( i >> 1 ) shifts the integer right by one place, which halves it: that’s
. Taking it away from a constant gives us the minus sign. And the constant is
.
So isn’t an error term to be swept under the rug. It is the exponent bias and the correction, carried through the algebra. The comes from the bias showing up on both sides: once on the left, and once halved and flipped on the right.
Let’s put some numbers in. With no correction at all, :
which in hex is 0x5f400000. That’s already eerily close to 0x5f3759df! Working backwards, 0x5f3759df is what you get with
. That is near the
that best fits the logarithm, but not quite on it.
Why not just use ? Because the bit hack isn’t the last step. Its guess still goes through a round of Newton’s method (more on that below), and what matters is how good the answer is after that. Running the whole function for every choice of and keeping the worst error gives this:
0x5f3759df sits right at the bottom of the curve. Whoever picked it either did this sum or tuned it by hand very patiently. Chris Lomont later searched for the best constant by brute force in his 2003 paper on this function, and landed on 0x5f375a86, which is within a whisker of the original.
So altogether we have found the logarithm of the inverse square root of as an integer.
How do we get our float back and remove that pesky logarithm?
y = * ( float * ) &i;
Fantastic, we just pull the inverse of same scam we did earlier. The shift we built into is exactly what this reading expects, so out comes a float very close to .
Since this is the inverse of the original hack we used, it is a poor-man’s un-logarithm. This step also conveniantly fixes our scaling problem of which we encountered above.
y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
// y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed
return y;
Now we are taking our victory lap around this function, what you see above is Newton’s method, which is an iterative equation that allows you to solve equations with linear approximations. It’s run once here just to gain a fair headroom of extra accuracy, since the rest of the function was very sketchy.
And then we just return our float!
This function is so damn fast, it actually beats lookup tables in terms of speed on the order of five times, a very significant speed increase.
Considering the sheer number of times an inverse square root is needed in computer graphics, it makes sense to go to these extremes.
And there you have it! I promised you the best approximation of all time, and I firmly believe this is it, or at least the most computed one.
The trick didn’t last. Intel added an inverse square root instruction to the Pentium III the same year Quake III shipped, and graphics hardware soon took the job over entirely. But for a while, every lit polygon on screen went through a line of code that took a logarithm by pretending a float was an integer.