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. :bigthink:

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 ( L 2 L_2 magnitude of the vector is 1, or more formally β€– 𝐯 ^ β€– 2 = 1 {\lVert\hat{\mathbf{v}}\rVert}_2 = 1 ) 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, 𝐯 ^ \hat{\mathbf{v}} .

Before I discuss why this is such a problem, I would first like to discuss how we get these vectors ( 𝐯 ^ \hat{\mathbf{v}} ).

Objects in computer graphics are polygons defined as a set of surfaces, which have 3D coordinates 𝐱 i = ( x i , y i , z i ) \mathbf{x}_i = (x_i,y_i,z_i) 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 𝐱 1 , 𝐱 2 , 𝐱 3 \mathbf{x}_1, \mathbf{x}_2, \mathbf{x}_3 we can now try and find a surface normal.

We can consider 𝐱 1 \mathbf{x}_1 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 𝐱 1 \mathbf{x}_1 to 𝐱 i \mathbf{x}_i where i i is 2 or 3. I am going to use the shorthand 𝐱 1 2 = 𝐱 2 βˆ’ 𝐱 1 = ( x 2 βˆ’ x 1 , y 2 βˆ’ y 1 , z 2 βˆ’ z 1 ) \mathbf{x}_1^2 = \mathbf{x}_2 - \mathbf{x}_1 = (x_2-x_1,y_2-y_1,z_2-z_1) 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).

Triangle with its two edge vectors Vertices 1, 2 and 3 run anticlockwise. Vector x 1-to-2 runs along the edge from vertex 1 to vertex 2, and x 1-to-3 from vertex 1 to vertex 3. x21 x31 1 2 3

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 ( 𝐱 1 2 Γ— 𝐱 1 3 = 𝐯 \mathbf{x}_1^2 \times \mathbf{x}_1^3 = \mathbf{v} ).

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:

Surface normal from the cross product The same triangle seen at an angle. The normal v rises from vertex 1, at right angles to both edge vectors, on the side the vertices run anticlockwise. x21 x31 v v = x21 Γ— x31 1 2 3

To humour ourselves, although not the goal of this post, we can test for polygon visibility. We have 𝐯 \mathbf{v} , 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 𝐰 \mathbf{w} , we can take the dot product, and if 𝐰 β‹… 𝐯 > 0 \mathbf{w} \cdot \mathbf{v} > 0 , the surface is facing us.

Back-face test Seen edge on. Left: the normal v leans towards the eye, so w dot v is positive and the surface is drawn. Right: v points away from the eye, w dot v is negative and the surface is culled. w v w β‹… v > 0 drawn w v w β‹… v < 0 culled

Normalised Normals

As I mentioned at the beginning of this post, we are interested in normalised surface normals, which I named 𝐯 ^ \hat{\mathbf{v}} .

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 𝐯 \mathbf{v} by it.

𝐯 β€– 𝐯 β€– 2 = 𝐯 ^ , such that β€– 𝐯 ^ β€– 2 = 1 \frac{\mathbf{v}}{\left\lVert\mathbf{v}\right\rVert_2} = \hat{\mathbf{v}}, \qquad \text{such that} \quad \left\lVert\hat{\mathbf{v}}\right\rVert_2 = 1 Where 𝐯 = ( x v , y v , z v ) β€– 𝐯 β€– 2 = x v 2 + y v 2 + z v 2 \mathbf{v} = (x_v,y_v,z_v) \qquad \left\lVert\mathbf{v}\right\rVert_2 = \sqrt{x_v^2 + y_v^2 + z_v^2}

so in one equation we can get our 𝐯 ^ \hat{\mathbf{v}} : 𝐯 ^ = ( x v , y v , z v ) x v 2 + y v 2 + z v 2 \hat{\mathbf{v}} = \frac{(x_v,y_v,z_v)}{\sqrt{x_v^2 + y_v^2 + z_v^2}}

Normalising v v points out past the unit circle. Dividing it by its length gives v hat, which points the same way but stops exactly on the circle: length 1. unit circle β€–vβ€–2 vv̂ v̂ = v / β€–vβ€–2

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 a = 1 b a = \frac{1}{\sqrt{b}} , then we can do 𝐯 ^ = a ( x v , y v , z v ) \hat{\mathbf{v}} = a (x_v,y_v,z_v) . This is just multiplication which should be fast! All we need is the impossible algorithm that finds a a 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 E E and M M .

The bits of 6.0 as a 32-bit float Sign bit 0, exponent E = 10000001 (129), mantissa M = 1 followed by 22 zeros. Read as a float the bits mean 1.5 times 2 squared, which is 6. Read as an integer the same bits are 1,086,324,736. sign 0 1 bit exponent E 10000001 8 bits mantissa M 10000000000000000000000 23 bits as a float(1 + M / 223) Γ— 2E βˆ’ 127= 1.5 Γ— 22 = 6as an integer223 E + M= 1,086,324,736

32 bit floats use the mantissa and exponent (ignoring sign) to define numbers as follows:

n float = ( 1 + M 2 23 ) 2 E βˆ’ 127 n_{\text{float}} = \left(1+ \frac{M}{2^{23}} \right) 2^{E-127}

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:

n int = 2 23 E + M n_{\text{int}} = 2^{23}E + M

Now we have the background covered, let’s dive into the hack behind this line of code.

We begin by taking the logarithm of n float n_{\text{float}} .

log 2 ( n f ) = log 2 ( ( 1 + M 2 23 ) 2 E βˆ’ 127 ) \log_2 ({n_f}) = \log_2 \left(\left(1+ \frac{M}{2^{23}} \right) 2^{E-127}\right) log 2 ( n f ) = log 2 ( 1 + M 2 23 ) + E βˆ’ 127 \log_2 ({n_f}) = \log_2 \left(1+ \frac{M}{2^{23}} \right) + {E-127}

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 log 2 ( 1 + x ) β‰ˆ x \log_2(1+x) \approx x for 0 ≀ x < 1 0 \le x < 1 .

We can do a little better than that. The line x x touches the curve at both ends and sits under it everywhere else, so it always comes up short. Lifting it by a small constant Οƒ \sigma splits the difference, so the error is spread evenly above and below the curve:

log 2 ( 1 + x ) β‰ˆ x + Οƒ \log_2(1+x) \approx x + \sigma

log2(1 + x) is close to x on [0, 1] The curve log2(1 + x) and the line x meet at 0 and 1 and never differ by more than 0.086, at x = 0.443. The line x + sigma, with sigma = 0.0430, splits that gap and runs through the middle of the curve. 00.5100.51 x widest gap: 0.086at x = 0.443 x + σσ, half of it: 0.0430 log2(1 + x) x

With Οƒ = 0 \sigma = 0 we’re back to the plain approximation, and the Οƒ \sigma that makes the worst error as small as possible is half the widest gap, about 0.0430 0.0430 . Hang on to Οƒ \sigma : it is most of the secret behind the magic number.

Using that in our logarithm, we are left with:

log 2 ( n f ) β‰ˆ M 2 23 + E βˆ’ 127 + Οƒ \log_2 ({n_f}) \approx \frac{M}{2^{23}} + E - 127 + \sigma

Now look at the integer again. Dividing n int n_{\text{int}} by 2 23 2^{23} gives E + M 2 23 E + \frac{M}{2^{23}} , which is exactly the shape above. So:

log 2 ( n f ) β‰ˆ n int 2 23 βˆ’ 127 + Οƒ \log_2 ({n_f}) \approx \frac{n_{\text{int}}}{2^{23}} - 127 + \sigma

Or, turning it round:

n int β‰ˆ 2 23 ( log 2 ( n f ) + 127 βˆ’ Οƒ ) n_{\text{int}} \approx 2^{23}\left(\log_2(n_f) + 127 - \sigma\right)

Interpreting a float as an int is a poor-man’s logarithm with base two! It is scaled by 2 23 2^{23} and shifted by 127 βˆ’ Οƒ 127 - \sigma , but it is a logarithm.

A float's bits, read as an integer, trace log2 The integer reading I of each float x, divided by 2 to the 23 and less 127, gives straight segments that meet the true log2 x curve at every power of two and sag just below it in between. βˆ’1012301248 log2 x I / 223 βˆ’ 127 dots: exact at powers of two x

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 b b and the answer we want a = 1 b a = \frac{1}{\sqrt{b}} . Take the logarithm of both sides:

log 2 ( a ) = βˆ’ 1 2 log 2 ( b ) \log_2(a) = -\frac{1}{2}\log_2(b)

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 I a I_a and I b I_b for the integer readings of a a and b b :

I a 2 23 βˆ’ 127 + Οƒ = βˆ’ 1 2 ( I b 2 23 βˆ’ 127 + Οƒ ) \frac{I_a}{2^{23}} - 127 + \sigma = -\frac{1}{2}\Bigl(\frac{I_b}{2^{23}} - 127 + \sigma\Bigr)

Multiply through by 2 23 2^{23} and gather the constants on one side:

I a = K βˆ’ 1 2 I b , K = 3 2 Γ— 2 23 Γ— ( 127 βˆ’ Οƒ ) I_a = K - \frac{1}{2} I_b, \qquad K = \frac{3}{2} \times 2^{23} \times (127 - \sigma)

That is the line of code, term for term. ( i >> 1 ) shifts the integer right by one place, which halves it: that’s 1 2 I b \frac{1}{2} I_b . Taking it away from a constant gives us the minus sign. And the constant is K K .

So K K isn’t an error term to be swept under the rug. It is the exponent bias and the Οƒ \sigma correction, carried through the algebra. The 3 2 \frac{3}{2} 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, Οƒ = 0 \sigma = 0 :

K = 3 2 Γ— 2 23 Γ— 127 = 1598029824 K = \frac{3}{2} \times 2^{23} \times 127 = 1598029824

which in hex is 0x5f400000. That’s already eerily close to 0x5f3759df! Working backwards, 0x5f3759df is what you get with Οƒ = 0.0450466 \sigma = 0.0450466 . That is near the 0.0430 0.0430 that best fits the logarithm, but not quite on it.

Why not just use 0.0430 0.0430 ? 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 Οƒ \sigma and keeping the worst error gives this:

Choosing sigma Worst relative error after one Newton step, against the correction sigma. With sigma = 0 (0x5f400000) it is 1.21 percent. The best fit to the logarithm, sigma = 0.0430, gives 0.201 percent. Quake's 0x5f3759df (sigma = 0.0450) gives 0.175 percent, close to the bottom of the curve. 0%0.5%1%00.020.040.060.08 Οƒ = 00x5f400000 1.214% best fit to log0x5f37bcb6 0.201% Quake0x5f3759df 0.175% Οƒ

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 b b 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 127 βˆ’ Οƒ 127 - \sigma shift we built into K K is exactly what this reading expects, so out comes a float very close to 1 b \frac{1}{\sqrt{b}} .

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 2 23 2^{23} 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.

One Newton step The curve f(y) = 1/y squared minus 6. The bit hack's guess y0 = 0.4206 sits on the curve; following the tangent down to zero lands at y1 = 0.4077, next to the true root 1/sqrt 6 = 0.4082. βˆ’101230.350.400.45 f(y) = 1/y2 βˆ’ 6 y0= 0.4206 the bit hack's guess y1= 0.4077 1/√6 = 0.4082 y

And then we just return our float!

Error before and after the Newton step Relative error of Q_rsqrt for x from 1 to 16. The bit hack alone is off by up to 3.44 percent; one Newton step brings that under 0.18 percent. βˆ’4%βˆ’2%0+2%+4%124816 bit hack alone: up to 3.4% offafter one Newton step: under 0.18% x (log scale)

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.