0x5f3759df - a true 'magic number’

`0x5f3759df`

The use of 'magic numbers' in code is a well-known antipattern, meaning a common but bad practice. It refers to the inclusion of set values without documentation of their purpose, making it a thorough pain in the arse for anyone other than the original author to maintain and fix code that relies on them.

0x5f3759df , or 1,597,463,007 in decimal notation, is one such magic number that appears in the Quake 3: Arena source code, in a genuinely beautiful hack committed by John Carmack.

Here comes the maths bit, concentrate

When you're doing 3D rendering, you have to find the square root of x (where x is a variable input) rather a lot.

Carmack's code contains a fast way of working out the inverse square root of x , which can be written as 1/sqrt(x) . With that information. we can work out sqrt(x) easily -

[](data:image/svg+xml,%3c?xml%20version='1.0'%20encoding='UTF-8'?%3e%3csvg%20version='1.1'%20viewBox='0%200%2024%2024'%20xmlns='http://www.w3.org/2000/svg'><path d='m17.426 16.84 0.51209 2.975c-0.31701 0.1707-0.82909 0.3292-1.5119 0.47551-0.69497 0.1585-1.5119 0.24385-2.4507 0.24385-2.6945-0.04877-4.7185-0.85348-6.0719-2.3897-1.3899-1.5485-2.0483-3.5114-2.0483-5.889 0.04877-2.8165 0.87786-4.9746 2.4873-6.4864 1.5606-1.5241 3.5602-2.3044 5.9743-2.3044 0.91444 0 1.707 0.085348 2.3654 0.23166 0.6584 0.14631 1.1461 0.30481 1.4631 0.4877l-0.73155 3.0359-1.268-0.41455c-0.4877-0.12193-1.0608-0.18289-1.707-0.18289-1.4021-0.012192-2.5726 0.43893-3.4871 1.3412-0.92663 0.89005-1.3899 2.2556-1.4387 4.0723 0.012193 1.6582 0.45112 2.9506 1.3168 3.9016 0.86567 0.93882 2.0727 1.4265 3.6456 1.4387l1.6216-0.14631c0.52428-0.09754 0.96321-0.23166 1.329-0.39016z' fill='%230288d1' stroke-width='1.2192'/%3e%3c/svg%3e)

x * (1/sqrt(x)) = sqrt(x)

The beauty here is that we don't have to be exactly correct. 3D modelling can operate in tolerances. If our result for sqrt(x) is out a little bit, that's okay - nobody will notice that the reflected light levels are off by a tiny amount. Carmack's code accepts this and embraces it. Here it is, trimmed a bit for clarity but with original comments -

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
  return y;
}

What it does is generate a guess for 1/sqrt(x) very, very quickly. With that information, Newton's algorithm (which is used to intelligently refine a guess for any mathematical function) only needs one iteration to get to a tolerable margin of error.

Turns out that, on the processors of the time, this is four times faster than asking the CPU to find the square root by itself.

So where's the magic?

Check out that line with the fairly colourful comments.