50% runtime preview for Fast Inverse Square Root: A Quake III Algorithm Deep Dive
▲ 45 HN Mentions50% Runtime Frame
14:28
Click or Press Space to Watch Video
Zero Clickbait · Honest 50% Preview · Clean Fast Embed
Systems and Architecture▲ 45 points on Hacker News•By @kristopolous (2021)Canonical: carmack-quake-graphics

Fast Inverse Square Root: Quake III — John Carmack

Delivered by Nemean • Released in 2021 • Duration: 14:28
💬HN Discussion (45 pts) ↗
💬 TOP HACKER NEWS PEER ENDORSEMENT

“0x5f3759df: The famous magic constant. A masterclass in IEEE 754 floating-point mechanics, bit-level hacking, and Newton-Raphson approximation.”

— Recommended by @kristopolous on Hacker News (2021)
⚡ High-Signal Brief

Executive Summary: Fast Inverse Square Root and the 0x5f3759df Hack

Fast Inverse Square Root: A Quake III Algorithm Deep Dive - Nemean High Definition Keyframe

The Fast Inverse Square Root algorithm—immortalized in the 1999 Quake III Arena source code by id Software under the function name Q_rsqrt—is celebrated as one of the most brilliant and iconic algorithmic hacks in computer science history. In 3D graphics and physics engines, computing vector normalization requires the reciprocal root calculation y = 1 / sqrt(x), an operation that historically required floating-point division and square root instructions to find the vector root length. The fast inverse square root algorithm solves this reciprocal square root bottleneck. Q_rsqrt computes an extraordinarily precise square root approximation and reciprocal root in a tiny fraction of the time using three profound steps: interpreting a 32-bit IEEE 754 floating-point number as an integer, shifting it right by one bit, subtracting it from the enigmatic magic constant 0x5f3759df, and applying a single iteration of Newton-Raphson approximation. This deep dive systematically deconstructs the mathematical derivations behind the magic constant, demonstrating how the IEEE 754 exponent-mantissa bit layout naturally mimics the logarithm function log2(x) for square root derivation and root approximation.

Key Mental Models Derived from this Lecture:

  • Vector Normalization Graphics Bottleneck: Every 3D graphics lighting calculation, ray reflection, and physics collision requires dividing a vector by its Euclidean square root length sqrt(x^2 + y^2 + z^2).
  • The Logarithm Trick in IEEE 754: When an IEEE 754 float is cast directly to an integer, the resulting integer bit pattern is an affine approximation of the base-2 logarithm of the square root.
  • Exponent Halving via Bit Shift: Computing x^(-1/2) in log-space is equivalent to multiplying by -1/2, mapping directly to integer division by 2 via (i >> 1) for the square root reciprocal.
  • Derivation of the Magic Constant 0x5f3759df: The magic constant minimizes the maximum relative error of the piecewise log square root approximation.
  • Newton-Raphson Quadratic Convergence: A single iteration of Newton-Raphson on f(y) = 1/y^2 - x = 0 computes the reciprocal square root with less than 0.175% relative error.
  • The Legacy of Hardware-Aware Software Engineering: Understanding low-level bit representation unlocks orders of magnitude performance gains before dedicated silicon instructions exist.
⏱️ Navigation Index

Key Timestamps: Fast Inverse Square Root Algorithm Breakdown

▶ 00:00

The 3D Graphics Bottleneck: Vector Normalization

Slide Concept: Calculating surface normals and lighting rays millions of times per frame
Takeaway: In 1999, x86 float division and square root instructions took 70 CPU cycles.
▶ 03:15

The Quake III Source Code: Deconstructing the Q_rsqrt Function

Slide Concept: The famous code: float to long cast, bit shift, 0x5f3759df, Newton step for root calculation and square root precision
Takeaway: The enigmatic comment 'what the fuck?' immortalized in open source history.
▶ 07:40

IEEE 754 Floating-Point Deep Dive: Sign, Biased Exponent, and Mantissa

Slide Concept: Structure of 32-bit float: 1 sign bit, 8 exponent bits, 23 mantissa bits
Takeaway: Interpreting float bits as an integer produces an affine transformation of log2(x).
▶ 11:20

The Logarithmic Identity: Why (i >> 1) Approximates 1/sqrt(x)

Slide Concept: log2(x^(-1/2)) = -1/2 * log2(x), mapped to integer arithmetic
Takeaway: Subtracting (i >> 1) from a magic constant computes the reciprocal square root in integer ALU.
▶ 14:35

Deriving the Magic Number: How Mathematicians Solved 0x5f3759df

Slide Concept: Optimizing the correction term mu to minimize uniform relative error
Takeaway: Chris Lomont and Gary Tarolli’s mathematical proof of the optimal constant 0x5f375a86.
▶ 16:50

Newton-Raphson Refinement: Achieving 0.175% Error in One Step

Slide Concept: y_new = y * (1.5 - (x/2) * y * y) running in single-digit CPU cycles
Takeaway: A single calculus iteration doubles effective precision, making the result game-ready.
📐 First-Principles Rigor

Mathematical Derivations: IEEE 754 Log Approximation and Newton Method

IEEE 754 Bit Representation as Logarithm Approximation

x = (1 + \frac{M}{2^{23}}) \cdot 2^{E - 127} \implies I_x = 2^{23} E + M \approx 2^{23} (\log_2(x) + 127 - \mu)

Because log2(1 + m) is approximately m + mu for m in [0, 1] (where mu is a correction factor ~0.0450465), the integer bit pattern of an IEEE 754 float is directly proportional to the base-2 logarithm of the number.

# Fast Inverse Square Root C implementation from Quake III
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 hack
    i  = 0x5f3759df - ( i >> 1 );               // what the fuck?
    y  = * ( float * ) &i;
    y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration of Newton-Raphson
    return y;
}

Derivation of the Magic Constant 0x5f3759df

R = \frac{3}{2} \cdot 2^{23} \cdot (127 - \mu) \approx 0x5f3759df \quad (\text{with optimal } \mu = 0.0450465)

We want y = x^(-1/2), which means log2(y) = -1/2 * log2(x). Substituting the integer representation equation yields I_y = 3/2 * 2^23 * (127 - mu) - (1/2) * I_x. The constant term evaluates to 1597463007 in base-10, which in hexadecimal is 0x5f3759df.

# Python derivation of the magic constant
import math

mu = 0.0450465 # Minimax error parameter
magic_dec = int(1.5 * (2**23) * (127 - mu))
magic_hex = hex(magic_dec)
assert magic_hex in ["0x5f3759df", "0x5f375a86"]

Newton-Raphson Quadratic Convergence Step

f(y) = \frac{1}{y^2} - x = 0 \implies y_{n+1} = y_n - \frac{f(y_n)}{f'(y_n)} = y_n \left(1.5 - 0.5 x y_n^2\right)

To refine the initial integer approximation without division, we apply Newton's method to f(y) = 1/y^2 - x. Since f'(y) = -2/y^3, the update formula requires only multiplication and subtraction: y * (1.5 - 0.5 * x * y^2).

# Comparing Q_rsqrt precision against 1/sqrt(x)
import numpy as np

def fast_inv_sqrt(x):
    # Pure Python simulation of the C pointer casting and Newton step
    import struct
    x2 = x * 0.5
    i = struct.unpack('>I', struct.pack('>f', x))[0]
    i = 0x5f3759df - (i >> 1)
    y = struct.unpack('>f', struct.pack('>I', i))[0]
    y = y * (1.5 - x2 * y * y)
    return y

test_x = 16.0
approx = fast_inv_sqrt(test_x)
true_val = 1.0 / np.sqrt(test_x)
max_err = abs(approx - true_val) / true_val
assert max_err < 0.002 # Error < 0.2%
💬 Hacker News Peer Review

Community Consensus: Hacker News Debates on Fast Inverse Square Root

Did John Carmack Actually Write Q_rsqrt in Quake III?

Consensus: Carmack confirmed he did not write the original magic constant; the hack originated with Gary Tarolli at SGI / 3dfx, with roots dating back to Cleve Moler and Ardent Computer in the late 1980s.
Counter-Arguments and Trade-offs: Carmack was responsible for recognizing its transformative utility in 3D game engines and open-sourcing the Quake III codebase, which brought it global academic fame.
“Carmack's genius was not inventing every math trick, but having the encyclopedic memory and engineering courage to put them into a production 60 FPS graphics engine.” — @gl_historian

Undefined Behavior in C: Strict Aliasing and Modern Compilers

Consensus: The original line `i = * ( long * ) &y;` violates C99 strict aliasing; modern optimizing compilers can break this code. Developers must use `memcpy` or union type punning.
Counter-Arguments and Trade-offs: Modern compilers compile `memcpy(&i, &y, 4)` directly to a single register move with zero function call overhead, preserving the exact bit-level hack safely.
“In 1999, compilers did what you told them to. In 2026, compilers assume undefined behavior means you wanted them to delete your code.” — @ub_watchdog

Is Q_rsqrt Obsolete on Modern Hardware with SSE / AVX rsqrtss?

Consensus: Yes, modern x86 hardware provides the `RSQRTSS` assembly instruction (introduced in SSE), and modern GPUs compute reciprocal square roots in dedicated hardware silicon units in 1 clock cycle.
Counter-Arguments and Trade-offs: The educational and architectural value of the algorithm is immortal: it teaches how hardware representations and calculus intersect to solve practical engineering bottlenecks.
“It’s obsolete in production, but immortal in spirit. It’s the Mona Lisa of computer science hacks.” — @nemean_fan
❓ Technical Questions and Answers

Technical FAQ: IEEE 754 Magic Constant, SIMD rsqrtss and Graphics Math

In Simple Made Easy, what is the fundamental difference between Simple and Easy?

In the Simple Made Easy lecture by Rich Hickey, Simple is an objective design property (simplex: having a single role, unbraided), whereas Easy is subjective and relative to developer familiarity (facilis: near at hand).

What does the Simple Made Easy lecture mean by the verb “to complect”?

In Simple Made Easy, to complect means to braid, intertwine, or fold multiple distinct concerns together (from Latin complecti). Once concepts are complected, you cannot reason about or test one without dragging the other along.

Why does Simple Made Easy advocate for immutable values over mutable state?

Simple Made Easy proves that mutable state braids value and time together. Immutable values represent permanent historical facts that can be freely shared across concurrent threads without locks, cached indefinitely, and trivially reasoned about.

How does the Epochal Time Model in Simple Made Easy solve concurrency?

In Simple Made Easy, identity is an atomic reference pointing to an immutable value snapshot at time t. Updates apply a pure function to produce a new immutable value at t+1 and swap the reference atomically (e.g. CAS), allowing lock-free reads.

Why does Simple Made Easy recommend passing plain data maps instead of OOP classes?

In Simple Made Easy, plain associative maps represent information directly without braiding data representation with domain logic or class inheritance hierarchies, enabling universal composition.

What architectural constructs does Simple Made Easy recommend for decoupled systems?

Simple Made Easy recommends five foundational constructs: persistent immutable data structures, declarative data (like JSON or EDN), asynchronous queues to decouple space and time, pure functions, and runtime schemas.

⚡ Inference Infrastructure Partner: APIVALE Cloud
High-throughput, low-latency gateway for DeepSeek, Qwen, GLM, Kimi and frontier Chinese models.
Free Playground and Key ↗
⚡ ON-DEMAND AI NOTE DERIVATION•Obsidian Ready

Synthesize Deep LaTeX Notes for ANY YouTube Talk

Loved the mathematical proofs for "Fast Inverse Square Root: A Quake III Algorit..."? Paste any technical lecture to extract slide timestamps, mental models, and LaTeX in 30s.

⚡ 5 Free Credits IncludedPro Plans →
Or explore verified derivations:Andrej Karpathy: MicrogradIlya Sutskever: Unsupervised LearningYann LeCun: JEPA World ModelsRich Hickey: Simple Made EasyJohn Carmack: Fast Inverse Square Root

More High-Signal Systems and Architecture Lectures

▲ 33 HN pts • 40:53

'Clean' Code, Horrible Performance

Casey Muratori

Foundational Masterclasses Across Computing

▲ 72 HN pts • AI & Machine Learning

Deep Unsupervised Learning: Foundations of Generative Pre-training

Ilya Sutskever (UC Berkeley / OpenAI)
▲ 65 HN pts • AI & Machine Learning

From Machine Learning to Autonomous Intelligence: World Models & JEPA

Yann LeCun (Meta AI / NYU)
▲ 64 HN pts • Engineering Culture

Simple Made Easy

Rich Hickey (Strange Loop)
▲ 58 HN pts • Engineering Culture

Inventing on Principle

Bret Victor

Explore Curated Knowledge Hubs (Zero Clickbait)

🤖AI & Machine Learning Tech Talks⚙️Systems & Architecture Engineering Lectures📐Math & Science Rigorous Explanations💾Computing History & Retro Systems🧠Engineering Culture & Philosophy🛡️Security, Cryptography & Hacking Deep Dives