-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA512 - --- title: "The Best Approximation of All Time" date: 2018-10-17T16:27:38+01:00 draft: false category: research excerpt: "0x5f3759df, and why I still love it." - --- # 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 ~wave: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$ magnitude of the vector is 1, or more formally ${\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 $\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 $\mathbf{x}_1, \mathbf{x}_2, \mathbf{x}_3$ we can now try and find a surface normal. We can consider $\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 $\mathbf{x}_1$ to $\mathbf{x}_i$ where $i$ is 2 or 3. I am going to use the shorthand $\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). ![A triangle with vertices 1, 2 and 3 running anticlockwise, and edge vectors x 1-to-2 and x 1-to-3 drawn from vertex 1](dirvectors.svg) - 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_ ($\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: ![The same triangle in 3D, with the normal v rising from vertex 1 at right angles to both edge vectors](normvectors.svg) 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 $\mathbf{w} \cdot \mathbf{v} > 0$, the surface is facing us. ![Back-face test seen edge on: when the normal v leans towards the eye, w dot v is positive and the surface is drawn; when it points away, w dot v is negative and the surface is culled](backface.svg) ## 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. $$\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 $$\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}}$: $$ \hat{\mathbf{v}} = \frac{(x_v,y_v,z_v)}{\sqrt{x_v^2 + y_v^2 + z_v^2}}$$ ![v points out past the unit circle; dividing by its length gives v hat, pointing the same way but stopping on the circle](normalise.svg) 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 = \frac{1}{\sqrt{b}}$, then we can do $\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$ 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. ```c 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: ```c 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$ and $M$. ![The 32 bits of 6.0: sign 0, exponent 10000001, mantissa 1 followed by 22 zeros, read once as a float and once as an integer](float-bits.svg) 32 bit floats use the mantissa and exponent (ignoring sign) to define numbers as follows: $$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_{\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_{\text{float}}$. $$ \log_2 ({n_f}) = \log_2 \left(\left(1+ \frac{M}{2^{23}} \right) 2^{E-127}\right)$$ $$ \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) \approx x$ for $0 \le x < 1$. We can do a little better than that. The line $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) \approx x + \sigma$$ ![log2(1 + x) plotted against the line x on 0 to 1, and the line x + sigma lifted by half the widest gap, 0.0430, so it runs through the middle of the curve](log-approx.svg) With $\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$. 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}) \approx \frac{M}{2^{23}} + E - 127 + \sigma$$ Now look at the integer again. Dividing $n_{\text{int}}$ by $2^{23}$ gives $E + \frac{M}{2^{23}}$, which is exactly the shape above. So: $$ \log_2 ({n_f}) \approx \frac{n_{\text{int}}}{2^{23}} - 127 + \sigma $$ Or, turning it round: $$ 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}$ and shifted by $127 - \sigma$, but it is a logarithm. ![A float's bits read as an integer, scaled and shifted, trace straight segments that meet log2 x at every power of two](int-log.svg) Hummus and Magnets [walks through this too](http://h14s.p5r.org/2012/09/0x5f3759df.html), and it's well worth a read. ### Where the magic number comes from ```c i = 0x5f3759df - ( i >> 1 ); // what the fuck? ``` Call the number we were given $b$ and the answer we want $a = \frac{1}{\sqrt{b}}$. Take the logarithm of both sides: $$ \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$ and $I_b$ for the integer readings of $a$ and $b$: $$ \frac{I_a}{2^{23}} - 127 + \sigma = -\frac{1}{2}\Bigl(\frac{I_b}{2^{23}} - 127 + \sigma\Bigr) $$ Multiply through by $2^{23}$ and gather the constants on one side: $$ 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 $\frac{1}{2} I_b$. Taking it away from a constant gives us the minus sign. And the constant is $K$. So $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 $\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, $\sigma = 0$: $$ 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 $\sigma = 0.0450466$. That is near the $0.0430$ that best fits the logarithm, but not quite on it. Why not just use $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: ![Worst error after one Newton step against sigma: 1.214 percent with sigma = 0 (0x5f400000), 0.201 percent at the best fit to the logarithm (0x5f37bcb6), and 0.175 percent with Quake's 0x5f3759df, at the bottom of the curve](magic-sigma.svg) `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$ as an integer. How do we get our float back and remove that pesky logarithm? ```c y = * ( float * ) &i; ``` Fantastic, we just pull the inverse of same scam we did earlier. The $127 - \sigma$ shift we built into $K$ is exactly what this reading expects, so out comes a float very close to $\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}$ which we encountered above. ```c 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 on f(y) = 1/y squared minus 6: the tangent at the bit hack's guess y0 = 0.4206 lands at y1 = 0.4077, next to the true root 0.4082](newton.svg) And then we just return our float! ![Relative error for x from 1 to 16: the bit hack alone is off by up to 3.4 percent; after one Newton step the error stays under 0.18 percent](rsqrt-error.svg) 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. -----BEGIN PGP SIGNATURE----- iQIyBAEBCgAdFiEEJtHIQX7gIiqRWdSs/RuAbpOsR8kFAmr+qYQACgkQ/RuAbpOs R8nZmA/4iP42xe68xp1DSJ+tirX+s2SLvHn/8i9FWqv6FLsSNf8Rp9nZL1xSKlmV gFhMjyowdpcEWHpx+cbzLNXS2KOxohzmceT5Eu0dul3ty7OXqqWejkRlQGl3+4w/ 7qz6+nlBJ8CfEHriimcMRBIm+yatgWi2ybiG9N/W8w5CzZSZlcHdLkPcKZNE0W02 JmkJov9DD+vcfFXeVqmHHgEtZwUvbjSADPBKevs/l2lObAlcS1FfeFOAFWlR3us0 2t5cf6JMfuQD2I9vwHLIeaRF3yePwVugQGli0soapLZE3lwdYexUuXEzYxb9tVTA 1JLhFk/l8s5CILt+KBEXYFAoukYpcBTPs7Egyi1aSzoVdGN6O5L1djI/Ltwlo2Vx SdmPVjuPj5npdINf2Wi0H507Uwy/Xjv13bIRJ1kRogQTUfbz/JjvGkC5VLV6rtWn 81/ZbolsBlSs5MAkWGMErJ+/t/Lhwio9kFphrg0USL6V1d3WJYypb/ETpd1ntU92 D880rHT7c16M++XI5Pgly/pNwGauv9Eb5KyPlJFeZ+QeNM/4UQeKhzuUMODjlLkF WNAiEDZ/syFads16/3D08eseIWzKNJSFX6dlFkHoN2e9w6H0sJNyM9COWktC2SNJ +RNh4k/r/xQK2jaf3HHr5XsBOXqw1Wrldz1wjOKiR/gzWYCvBA== =a6jJ -----END PGP SIGNATURE-----