Deterministic fixed-point math

Deep dive

Decision table

Code

use std::ops::{Add, Mul, Neg, Sub};

/// Q16.16 fixed point: value = raw / 65536. Range ±32768, step 1.5e-5.
#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Debug, Default, Hash)]
pub struct Fx(pub i32);

impl Fx {
    pub const ONE: Fx = Fx(1 << 16);
    pub const fn from_int(i: i32) -> Fx { Fx(i << 16) }
    /// Only for loading authored data offline / debug printing; never in the simulation.
    pub fn from_f64_offline(x: f64) -> Fx { Fx((x * 65536.0).round() as i32) }
    pub fn to_f64(self) -> f64 { self.0 as f64 / 65536.0 }

    /// a / b, truncated toward zero. Panics on b == 0 (identically on every platform).
    pub fn div(self, b: Fx) -> Fx { Fx((((self.0 as i64) << 16) / b.0 as i64) as i32) }

    pub fn sqrt(self) -> Fx {
        assert!(self.0 >= 0);
        Fx(isqrt((self.0 as u64) << 16) as i32) // sqrt(raw·2^16) = sqrt(x)·2^16
    }
}

// Wrapping everywhere: Rust panics on overflow in debug and wraps in release;
// explicit wrapping makes both builds (and every platform) agree.
impl Add for Fx { type Output = Fx; fn add(self, o: Fx) -> Fx { Fx(self.0.wrapping_add(o.0)) } }
impl Sub for Fx { type Output = Fx; fn sub(self, o: Fx) -> Fx { Fx(self.0.wrapping_sub(o.0)) } }
impl Neg for Fx { type Output = Fx; fn neg(self) -> Fx { Fx(self.0.wrapping_neg()) } }
impl Mul for Fx {
    type Output = Fx;
    fn mul(self, o: Fx) -> Fx {
        // 64-bit product, round half up, arithmetic shift (defined for negatives in Rust)
        Fx(((self.0 as i64 * o.0 as i64 + (1 << 15)) >> 16) as i32)
    }
}

/// Bit-by-bit integer square root: floor(sqrt(n)), no floats, no division.
pub fn isqrt(mut n: u64) -> u64 {
    let (mut res, mut bit) = (0u64, 1u64 << 62);
    while bit > n { bit >>= 2; }
    while bit != 0 {
        if n >= res + bit { n -= res + bit; res = (res >> 1) + bit; } else { res >>= 1; }
        bit >>= 2;
    }
    res
}

/// atan(2^-i) in binary angle units (2^32 = one full turn), i = 0..24.
const ATAN: [i64; 24] = [536870912, 316933406, 167458907, 85004756, 42667331, 21354465,
    10679838, 5340245, 2670163, 1335087, 667544, 333772, 166886, 83443, 41722, 20861,
    10430, 5215, 2608, 1304, 652, 326, 163, 81];
const CORDIC_K: i64 = 652032874; // prod 1/sqrt(1 + 2^-2i) for 24 steps, in Q2.30

/// (sin, cos) of a binary angle (u32 wraps at one turn, so angle arithmetic never
/// needs range reduction). CORDIC: shifts and adds only, bit-identical everywhere.
pub fn sin_cos(angle: u32) -> (Fx, Fx) {
    let mut z = angle as i32 as i64;           // (-180°, 180°]
    let mut flip = false;
    if z > 1 << 30 || z < -(1 << 30) {         // outside ±90°: rotate by 180°
        z = (angle.wrapping_add(1 << 31)) as i32 as i64;
        flip = true;
    }
    let (mut x, mut y) = (CORDIC_K, 0i64);     // Q2.30, pre-scaled by the CORDIC gain
    for i in 0..24 {
        let (dx, dy) = (y >> i, x >> i);
        if z >= 0 { x -= dx; y += dy; z -= ATAN[i]; } else { x += dx; y -= dy; z += ATAN[i]; }
    }
    let to_fx = |v: i64| Fx(((v + (1 << 13)) >> 14) as i32); // Q2.30 → Q16.16, rounded
    let (s, c) = (to_fx(y), to_fx(x));
    if flip { (-s, -c) } else { (s, c) }
}

/// SplitMix64: tiny, fully specified PRNG. Same seed → same stream on every platform.
pub struct Rng(pub u64);
impl Rng {
    pub fn next_u64(&mut self) -> u64 {
        self.0 = self.0.wrapping_add(0x9E3779B97F4A7C15);
        let mut z = self.0;
        z = (z ^ (z >> 30)).wrapping_mul(0xBF58476D1CE4E5B9);
        z = (z ^ (z >> 27)).wrapping_mul(0x94D049BB133111EB);
        z ^ (z >> 31)
    }
    /// Uniform in [0, n) by multiply-high (Lemire) on the top 32 bits; bias < n / 2^32, no division.
    pub fn below(&mut self, n: u32) -> u32 { ((self.next_u64() >> 32) * n as u64 >> 32) as u32 }
}

Checked against f64 over 2²⁰ angles: CORDIC's sine and cosine stay within 0.51 LSB of Q16.16 (7.7 × 10⁻⁶). Rng(1).next_u64() returns 0x910a2dec89025cc1 on every platform.

Efficiency

Cost: a Q16.16 multiply is one 32x32 to 64-bit integer multiply plus a shift; division is the slow op, order of 10-90 cycles for 64-bit idiv on x86 versus 3-4 for a multiply. The bound is ALU latency, not memory; fixed point costs no more than float and removes FP-mode dependence.

Levers:

• Precompute reciprocals ((1<<32)/d) for reused divisors — turns divides into multiplies (order of 10x per op) — repeated division by one value.
• Table or CORDIC trig generated offline — no libm call, identical results on all targets (Volder, 1959) — angles and rotations in the simulation.
• 64-bit formats only where the range needs them; Q16.16 i32 elsewhere — halves state and hash size (order of) — world coordinates vs local quantities.
• Binary angles in u16/u32 — free wraparound, no range reduction — headings.
• Hash canonical state every N ticks — detects drift early — any replicated simulation.

Naive → standard → state of the art:

• Plain f32 with default compiler flags · fast, but FMA, x87, fast-math and libm change bits per build
• Strict-flag floats with own trig, tested on every target · same speed, needs per-target tests (Box2D v3 approach)
• Integer fixed point with offline tables and hashed state checks · bit-identical by construction, cost of wider multiplies

Implementation notes

• Formats: Q16.16 (i32) for 2D games with world units of order of metres; Q32.32 or Q48.16 (i64, i128 for products) for big worlds. Keep one format in the simulation; convert only at the edges (input, rendering).
• Rounding: >> on signed integers is an arithmetic shift in Rust (floor); C++20 guarantees it too, older C/C++ left it implementation-defined (all mainstream compilers do arithmetic). Add 1 << (FRAC-1) before shifting to round to nearest. Integer division truncates toward zero; that is deterministic, but a/b*b ≠ a for negatives.
• Overflow: Rust panics on i32 overflow in debug and wraps in release; use wrapping_*, checked_* or saturating_* explicitly so both builds compute the same thing. In C/C++, signed overflow is undefined behaviour and optimisers exploit it; use unsigned or int64_t intermediates.
• Division: 64-bit idiv costs order of 10-90 cycles on x86 depending on the CPU generation, versus 3-4 for a multiply; precompute reciprocals (recip = (1<<32)/d once) where the divisor is reused.
• Trig: CORDIC (shift-add, shown), a quarter-wave lookup table with linear interpolation, or a fixed-point polynomial. Generate tables offline and commit them as integer constants; computing them at startup with the platform sin reintroduces the problem.
• Floats done right (if you keep them): -ffp-contract=off (GCC/Clang), no -ffast-math/-Ofast, SSE2 instead of x87 on 32-bit x86 (-mfpmath=sse -msse2), own sin/cos/atan2, fixed reduction order in parallel sums, same denormal mode (don't let a plugin set FTZ/DAZ), and in Rust avoid f32::sin etc. for simulation state. Box2D v3 reaches cross-platform float determinism this way: FMA disabled and its own trig approximations.
• Desync detection: hash the simulation state every N ticks (e.g. 64-bit hash over a canonical serialisation) and exchange hashes; on mismatch dump both states for diffing.
• Collections: deterministic iteration only (Vec, BTreeMap, insertion-ordered maps); Rust's HashMap uses a random seed per process.

Pitfalls

• One float sneaks in: a f32 animation curve, a physics-engine query, as f32 for a distance check. Ban float types in simulation modules (lint or a newtype-only API).
• Converting authored data (level files in floats) at load time with from_f64 on each client: fine only if the conversion is exact or done once offline; ship fixed-point data.
• Q16.16 multiply of two values above ~181 overflows i32 after the shift (181² ≈ 32768); range-check gameplay quantities or use wider formats.
• Taking sqrt of squared distances in Q16.16: squares overflow early; compare squared distances in i64 instead.
• C's rand(), std::uniform_int_distribution, std::normal_distribution: the C++ engines (e.g. mt19937) are fully specified, the distributions are not; outputs differ between standard libraries.
• Same source, different binaries: compiler versions, -march=native, or runtime CPU dispatch (AVX2 path vs SSE path in a library) change float results. Pin flags and ship identical builds.

Implementations

Sources

• IEEE Std 754-2008 / 754-2019, IEEE Standard for Floating-Point Arithmetic (§9: recommended, not required, correctly rounded functions). standard
• David Monniaux, The pitfalls of verifying floating-point computations, ACM TOPLAS, 2008. paper
• Bruce Dawson, Floating-Point Determinism, randomascii blog, 2013. post
• Glenn Fiedler, Floating Point Determinism, Gaffer On Games, 2010. post
• Erin Catto, Determinism, box2d.org blog, 2024. post
• Jack E. Volder, The CORDIC Trigonometric Computing Technique, IRE Transactions on Electronic Computers, 1959. paper
• Paul Bettner, Mark Terrano, 1500 Archers on a 28.8: Network Programming in Age of Empires and Beyond, GDC 2001.
• Guy L. Steele Jr., Doug Lea, Christine H. Flood, Fast Splittable Pseudorandom Number Generators, OOPSLA 2014 (SplitMix64). paper
• Trail of Bits, Not So Smart Contracts: Cosmos, Non-determinism. page
• Arm, CMSIS-DSP Library. docs
• Solidity docs, Types: fixed point numbers. docs
• WebAssembly Core Specification, Numerics. spec