A-TIER resource
Quake III fast inverse square root — the 0x5f3759df bit hack explained
100k ft — What is this?
Quake III fast inverse square root — the 0x5f3759df bit hack explained
50k ft — Why care?
Explains Quake III's four-line fast inverse square root: reinterpret float bits as an integer (which behaves logarithmically), shift right to halve the exponent, subtract from magic constant 0x5f3759df, then one Newton-Raphson step to bring error under 0.175%. Covers why normalization was costly on 1999 Pentiums and the constant's lineage through 3dfx and Cleve Moler.
10k ft — Key takeaways
• Float bits read as an integer approximate a logarithm
• One Newton-Raphson pass turns a 1% approximation into under 0.18%
• The constant balances exponent bias 127 against linear error
5k ft — Tools & techniques
Quake III Arena
Newton-Raphson iteration, code generation, float bit reinterpretation
1k ft — Deep-dive / try it
In 1999, id Software open-sourced _Quake III Arena_. Hidden inside was a four-line function calculating the inverse square root 400% faster than CPU silicon hardware, powered by an unexplained hexadecimal constant: `0x5f3759df`.
#programming #math #computerscience #quake3 #algorithms #coding #graphics #vox #gamedev
#quake iii #fast inverse square root #0x5f3759df #computer history #graphics programming #john carmack #algorithms #math explained #software engineering
Transcript excerpt
In 1999, ID Software open-sourced Quake 3. Buried inside the game engine was a four-line mathematical mystery. It calculated the inverse square root four times faster than silicon hardware, driven by an unexplained hexadecimal number, 0x5F3759DF, and the developer comments simply read, what the fuck. Why was this function so desperate? In 3D graphics, every ray of light, every shadow and every surface reflection requires normalizing vector angles. You divide the vector by its length, one over the square root of x. But on a 1999 Pentium, floating-point division and square root took over 70 clock cycles. Computing millions of them per frame brought CPUs to their knees. The breakthrough started with a bizarre trick. Inside computer memory, a 32-bit floating-point number has a sine, an exponent and a fraction. If you treat those raw bits not as a float, but as an integer, the number behaves logarithmically. Shifting the bits right by one divides the exponent by two. In other words, a simple bit shift calculates a square root. To get the inverse square root, you negate the exponent and subtract the bits from a magic number. That constant had to balance the floating-point exponent bias of 127 and minimize piecewise linear error. When mathematician Greg Walsh calculated the optimal bias, the formula produced 1,597,463,007 0x5F3759DF. The bit-level hack was fast, but it was only an approximation, with about 1% error. To make it game-ready, the code ran a single pass of…