The code became famous because it looked like a spell.

float bits -> integer
magic - half the bits
integer bits -> float
repair it once with Newton

That is not how numerical algorithms are supposed to introduce themselves.

The function computes an approximation to

\[\frac{1}{\sqrt{x}}.\]

In a 3D engine, that expression is everywhere. To normalize a vector (v), compute (v \cdot v), take an inverse square root, and multiply:

\[\hat v = v \cdot \frac{1}{\sqrt{v \cdot v}}.\]

Lighting, collision normals, camera vectors, reflections, and physics all keep asking for unit vectors. In the software-rendering and early hardware-accelerated era, a fast approximate inverse square root could be worth real frame time.

The version made famous by Quake III Arena lives in id Software’s released source as Q_rsqrt in q_math.c.1 But the best way to read the hack is not as a Quake anecdote. It is a tiny systems lesson:

representation is a model.

IEEE single-precision floats store a sign bit, an eight-bit biased exponent, and a 23-bit fraction.2 If you reinterpret a positive float as an integer, the resulting integer is not the logarithm of the number. But over a useful range, it behaves like a cheap affine proxy for (\log_2 x). And if

\[y = \frac{1}{\sqrt{x}},\]

then

\[\log_2 y = -\frac{1}{2}\log_2 x.\]

The mystery line is doing that operation crudely in the integer encoding. The right shift divides the bit-pattern proxy by two. The magic constant supplies the offset. The result is not accurate enough to trust, but it is close enough for one Newton step to repair.

The Repair Step

The Newton update used by the algorithm is:

\[y_{n+1} = y_n\left(\frac{3}{2}-\frac{x}{2}y_n^2\right).\]

This comes from solving (1/y^2 - x = 0). If (y_n) is already close to (1/\sqrt{x}), the update squares away a lot of the relative error in one multiply-heavy pass.

Chris Lomont’s 2003 note is still the compact explanation I like most: it asks where 0x5f3759df came from, reports a maximum relative error of about 0.00175228 for the one-step version over all floats, and shows that nearby constants can slightly improve the worst case.3 Charles McEniry later walked through the bit-level derivation in more detail, including the logarithm approximation and candidate constants such as 0x5f375a86.4

The lab below recreates the trick in JavaScript using typed-array reinterpretation, then audits the result. It is not benchmarking speed. Modern hardware and compilers have their own square-root and reciprocal-square-root paths; the x86 RSQRTSS instruction, for example, is explicitly an approximate reciprocal square-root operation.5 The point here is accuracy mechanics: which part is the bit guess, which part is Newton, and how much visible normal error remains.

The Audit tile checks float32 bit reinterpretation, the Quake seed for x=1, the known one-step output, the classic error range, the second Newton step, the Lomont constant, and the local constant sweep.

At the default settings, the raw bit guess is allowed to be quite rough: the maximum relative error over the displayed grid is about 3.44%. One Newton step brings the maximum relative error down to about 0.1751%. A second step drops it to about 0.000473%.

That is the shape of the hack:

bits give the first shove
Newton repairs the guess
the application sets the error budget

The default one-step version is not “correct” in the IEEE sense. It is an engineering bargain. For many old graphics uses, a normal-length error below two tenths of a percent was often fine. For numerical simulation, geometry kernels, or anything that accumulates error through many steps, it might not be fine at all.

What the Constant Is Buying

The constant is not arbitrary. It chooses a line through the float encoding that will become a line through a logarithmic approximation.

For positive normal floats, the integer interpretation increases with the exponent and then with the fraction. If you squint, that integer is proportional to:

\[E + m,\]

where (E) is the biased exponent and (m) is the fractional part. That is a cheap, piecewise-linear sketch of (\log_2 x). To approximate (-\frac12 \log_2 x), halve the integer proxy and subtract it from a constant.

The lab’s “constant audition” panel deliberately avoids pretending there is only one magic number. On the default finite grid, a nearby offset can very slightly beat the Quake constant. Lomont found 0x5f375a86 as a better single constant under his full-float criterion.3 McEniry derives a closely related value from an explicit error-balancing argument.4

So the real trick is not memorizing 0x5f3759df. The trick is noticing that the bit pattern can be spent as a log-domain initial guess.

Who Wrote It?

The folk version says “John Carmack wrote the weird line.” The evidence is more interesting.

Rys Sommefeldt’s Beyond3D investigation asked Carmack, Terje Mathisen, and Gary Tarolli about the code. Carmack replied that it was not his and probably not Michael Abrash’s.6 Tarolli recognized the code, remembered using and tweaking constants, but did not claim original authorship. The follow-up article reports that Greg Walsh contacted Beyond3D after publication and identified his Ardent Computer implementation as the source, with Cleve Moler as the inspiration for the Newton-iteration approach.7

That path is more believable than the myth because good hacks travel. A useful approximation can pass through workstations, graphics companies, engine code, forum posts, and finally a source release before the internet gives it a name.

The source release mattered. Without the Quake III GPL code, the algorithm might have remained one more private graphics trick. With the source open, the snippet became inspectable, portable, debatable, and teachable.

The Portability Footnote Is Not Optional

The original C idiom type-puns through pointer casts. Modern C and C++ programmers should be suspicious of copying it literally. Strict aliasing, integer width, endianness assumptions, compiler optimizations, fast-math flags, denormals, and target-specific reciprocal-square-root instructions all change the practical question.

The question today is rarely “should I paste the Quake function?” It is closer to:

  • What accuracy do I need, in relative error and in the downstream quantity?
  • Does the platform already provide a reciprocal-square-root approximation?
  • Does one Newton refinement after a hardware estimate meet the error budget?
  • Is the approximation deterministic enough for replay, networking, or tests?
  • Does the compiler transform preserve the semantics I promised?

The beautiful part of the hack survives those caveats. It teaches a habit: when the representation is structured, sometimes the first approximation is already in the bits.

The square root was not computed.

It was found hiding in the exponent, then repaired.

  1. id Software, q_math.c in the Quake III Arena GPL source release. The Q_rsqrt implementation appears near the end of the file with the 0x5f3759df constant and one active Newton step. ↩

  2. David Goldberg, “What Every Computer Scientist Should Know About Floating-Point Arithmetic”, ACM Computing Surveys, 1991. The Oracle reprint includes the IEEE floating-point background and error terminology. ↩

  3. Chris Lomont, “Fast Inverse Square Root”, 2003. ↩ ↩2

  4. Charles McEniry, “The Mathematics Behind the Fast Inverse Square Root Function Code”, 2007. ↩ ↩2

  5. Intel, “Intel C++ Intrinsics Reference”. The reference describes reciprocal and reciprocal-square-root SIMD approximation intrinsics as faster when their inaccuracy is acceptable. ↩

  6. Rys Sommefeldt, “Origin of Quake3’s Fast InvSqrt()”, Beyond3D, 29 November 2006. ↩

  7. Rys Sommefeldt, “Origin of Quake3’s Fast InvSqrt() - Part Two”, Beyond3D, 19 December 2006. ↩