Quake Fast Inverse Square Root in Rust

Rust can implement this algorithm without unsafe pointer casts by using f32::to_bits() and f32::from_bits(). These methods preserve the exact IEEE-754 bit pattern, which is what Quake's approximation requires. You will also learn why as is not appropriate here, why this algorithm uses f32, and when modern code should use sqrt() instead.

Quake's fast inverse square root estimates this value:

1 / √x

It does not calculate √x directly. The famous algorithm works in two stages:

1. It treats the IEEE-754 bit pattern of a floating-point number as an integer.
2. It uses a magic constant to produce a quick initial estimate, then improves it with one Newton-Raphson iteration.

The crucial operation is bit reinterpretation. In C, the original code uses pointer casts such as *(int *)&x. In Rust, the safe, explicit equivalents are:

• x.to_bits() — view an f32 value as its u32 IEEE-754 bit pattern.
• f32::from_bits(bits) — create an f32 from a u32 bit pattern.

This differs completely from x as i64. An as cast performs a numeric conversion: for example, 100.0_f32 as i32 becomes the integer 100. The Quake algorithm needs the encoded floating-point bits instead.

The original algorithm was useful on older hardware where square roots were relatively expensive. On modern CPUs, x.sqrt() is generally clearer, accurate, and often highly optimized. The algorithm remains a useful lesson in floating-point encoding, bit manipulation, and numerical approximation.

Think of a floating-point number as a package with a barcode.

• A numeric conversion, such as 100.0_f32 as i32, opens the package and writes its numeric value in a different format: 100.
• Bit reinterpretation, such as 100.0_f32.to_bits(), does not open or change the package. It reads the barcode printed on it.

Quake's algorithm needs the barcode because the exponent and mantissa layout of IEEE-754 floating-point values lets the integer operation create a rough estimate of 1 / √x.

Newton-Raphson refinement is like correcting a rough measurement. The bit trick gives a quick first guess; one mathematical correction makes that guess substantially better.

For an f32, use to_bits and from_bits:

let value: f32 = 100.0;
let bits: u32 = value.to_bits();
let same_value: f32 = f32::from_bits(bits);

assert_eq!(value, same_value);

A direct Rust version of the Quake approximation is:

fn fast_inv_sqrt(x: f32) -> f32 {
    let x_half = 0.5 * x;

    // Reinterpret float bits as an unsigned 32-bit integer.
    let bits = x.to_bits();

    // Make an initial approximation using the Quake magic constant.
    let estimate_bits = 0x5f3759df_u32.wrapping_sub(bits >> 1);
    let mut y = f32::from_bits(estimate_bits);

    // One Newton-Raphson refinement step.
    y = y * (1.5 - x_half * y * y);
    y
}

fn main() {
    let x = 100.0_f32;

    println!("fast estimate: {}", fast_inv_sqrt(x));
    println!("accurate value: {}", 1.0 / x.sqrt());
}

For 100.0, the result is close to 0.1, because 1 / √100 = 0.1.

Notice that this function returns y directly. The original C function already returns an inverse square root. Returning 1.0 / y would instead produce an approximation of √x.

Consider this call:

let result = fast_inv_sqrt(4.0_f32);

The target result is 1 / √4, which is 0.5.

1. x_half becomes 2.0.

   let x_half = 0.5 * 4.0;
   

2. to_bits() retrieves the IEEE-754 representation of 4.0.

   let bits = 4.0_f32.to_bits();
   

   This is not the number 4; it is the integer containing the float's stored bits.

3. The integer is shifted right and subtracted from the magic constant.

   let estimate_bits = 0x5f3759df_u32.wrapping_sub(bits >> 1);
   

   The resulting bits represent a float that is already a rough approximation of 1 / √4.

4. from_bits() interprets those new bits as an f32.

   let mut y = f32::from_bits(estimate_bits);
   

5. Newton-Raphson refinement improves the estimate.

   y = y * (1.5 - x_half * y * y);
   

6. y is returned as the approximate inverse square root. One iteration is fast but not perfectly accurate; further iterations improve accuracy.

Bit-level float reinterpretation and inverse square roots appear in several areas:

• Game and graphics engines: normalizing 2D or 3D vectors requires a vector length and often an inverse length.
• Physics simulations: directions, collision normals, and velocities are frequently normalized.
• Signal processing: approximate reciprocal and inverse-root operations can occur in performance-sensitive numeric code.
• Binary file formats: reading a float encoded as four bytes often involves constructing a u32 and calling f32::from_bits.
• Protocol and hardware work: bit patterns may need to be preserved exactly, including NaN payloads and signed zero.

For ordinary application code, use the standard-library operation instead:

let inverse_root = 1.0_f32 / x.sqrt();

In production Rust, developers usually separate a fast approximation from a safe public API.

A practical wrapper can define sensible behavior for invalid inputs:

fn inverse_sqrt(x: f32) -> f32 {
    if x.is_nan() || x < 0.0 {
        return f32::NAN;
    }
    if x == 0.0 {
        return f32::INFINITY;
    }
    if x.is_infinite() {
        return 0.0;
    }

    fast_inv_sqrt(x)
}

Common real-project patterns include:

• Validation or guard clauses: reject negative input before applying an approximation designed for positive values.
• Benchmarking first: compare the approximation with 1.0 / x.sqrt() on the target machine before choosing it.
• Error tolerance tests: test whether the approximation is accurate enough for the task.
• Clear naming: call the function fast_inv_sqrt, not sqrt, because its output is 1 / √x.
• Feature-specific optimization: keep specialized numeric tricks in a small, documented module rather than spreading them across an application.

If maximum accuracy or predictable IEEE-754 edge-case behavior matters, prefer the standard library calculation.

Using as instead of reinterpreting bits

This performs numeric conversion and breaks the algorithm:

let i = x as i64; // Wrong for Quake's bit hack

Use this instead:

let i: u32 = x.to_bits();

Using f64 with the f32 magic constant

The constant 0x5f3759df and the bit layout assumed by the algorithm are for 32-bit IEEE-754 float values. In Rust, that means f32, not f64.

fn fast_inv_sqrt(x: f32) -> f32 {
    // Correct type for this particular algorithm.
    # let _ = x;
    0.0
}

An f64 has a different exponent size, mantissa size, and total bit width, so this constant cannot simply be reused.

Returning the reciprocal unnecessarily

The Quake formula returns inverse square root already:

let inv_root = fast_inv_sqrt(100.0);
// inv_root is approximately 0.1

This changes the meaning to square root:

let root = 1.0 / fast_inv_sqrt(100.0);

Assuming it is exact

One Newton-Raphson iteration gives an approximation. Do not use it where a small numerical error is unacceptable.

Ignoring zero, negative values, infinity, and NaN

The bit trick is intended for positive, finite inputs. Add explicit handling if your API must support all f32 values.

Recreating C pointer casts

Avoid translating *(int *)&x directly. Rust's to_bits and from_bits clearly state the intent and avoid unsafe aliasing concerns.

For Rust floating-point values, related methods include:

let f: f32 = -0.0;
let bits: u32 = f.to_bits();
let restored: f32 = f32::from_bits(bits);

let d: f64 = 1.0;
let double_bits: u64 = d.to_bits();
let restored_double: f64 = f64::from_bits(double_bits);

Use u32 for f32 bits and u64 for f64 bits.

// Exact bit reinterpretation for f32
let bits: u32 = value.to_bits();
let value_again: f32 = f32::from_bits(bits);

// Quake-style inverse square root, for positive finite f32 input
fn fast_inv_sqrt(x: f32) -> f32 {
    let half = 0.5 * x;
    let bits = 0x5f3759df_u32.wrapping_sub(x.to_bits() >> 1);
    let y = f32::from_bits(bits);
    y * (1.5 - half * y * y)
}

// Accurate and readable alternative
let inverse_root = 1.0_f32 / x.sqrt();

Rules to remember:

• as converts a value numerically; it does not preserve float bits.
• Use to_bits and from_bits for bit reinterpretation.
• This magic constant is designed for f32, not f64.
• The result estimates 1 / √x.
• The bit trick is intended for positive finite inputs.
• Add another Newton-Raphson iteration if accuracy matters more than preserving the original algorithm's speed profile.

Can Quake's fast inverse square root be written safely in Rust?

Yes. Use f32::to_bits() and f32::from_bits() instead of C pointer casts. No unsafe code is needed for the bit reinterpretation.

Why does x as i64 not work?

as numerically converts x. For example, 100.0_f32 as i64 is 100. The algorithm instead needs the binary IEEE-754 encoding of 100.0.

Why should the Rust version use u32?

An f32 occupies 32 bits, and to_bits() returns u32. Unsigned bit manipulation also avoids treating bit patterns as signed numeric values.

Can I use this exact constant with f64?

No. The constant relies on the 32-bit IEEE-754 layout of f32. An f64 requires a different approximation strategy and constants.

Does fast_inv_sqrt(x) return sqrt(x)?

No. It returns approximately 1 / sqrt(x). Take its reciprocal only if you specifically need an approximate square root.

Is the Quake algorithm faster than sqrt() in modern Rust?

Not necessarily. Modern processors and compilers optimize square root operations well. Benchmark the real workload on the hardware you support before choosing the approximation.

How accurate is one iteration?

It is a useful approximation, not an exact result. One Newton-Raphson iteration greatly improves the initial bit estimate; additional iterations improve accuracy further.

What should happen for zero or negative input?

Mathematically, inverse square root is infinite at zero and not a real number for negative values. Handle these cases explicitly if your function accepts arbitrary inputs.

• IEEE-754 floating-point representation — explains the sign, exponent, and fraction bits that make the approximation possible.
• Rust to_bits and from_bits — safe APIs for preserving and reinterpreting floating-point bit patterns.
• Numeric casting with as — contrasts numeric conversion with bit reinterpretation.
• Bitwise operators — covers shifts, masks, and integer arithmetic on binary representations.
• Newton-Raphson method — explains the refinement formula used after the initial estimate.
• Floating-point precision — helps evaluate approximation error and edge cases such as NaN and infinity.
• Vector normalization — a common graphics use case for inverse square roots.