nordisk/knut

crates/knut-rel2graph-bench/src/prng.rs

//! A tiny, dependency-free, **deterministic** PRNG (SplitMix64).
//!
//! The whole harness must be reproducible: the same seed + the same scale
//! factor must produce the exact same relational rows on every run and every
//! machine, so a correctness assertion or a timing number is meaningful. That
//! rules out `rand` (thread-seeded) and anything touching the wall clock.
//! SplitMix64 is the reference finalizer used to seed xoshiro; it is fast,
//! stateless-per-step, and its output sequence is fixed by the seed alone.

/// A seeded SplitMix64 generator. `Clone` so a caller can fork an independent,
/// reproducible sub-stream (e.g. one per table) from a base seed.
#[derive(Debug, Clone)]
pub struct Rng {
    state: u64,
}

impl Rng {
    /// Create a generator from a fixed seed. Same seed ⇒ same sequence.
    pub fn new(seed: u64) -> Self {
        Rng { state: seed }
    }

    /// Next raw 64-bit value (the SplitMix64 step).
    #[inline]
    pub fn next_u64(&mut self) -> u64 {
        self.state = self.state.wrapping_add(0x9E37_79B9_7F4A_7C15);
        let mut z = self.state;
        z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
        z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
        z ^ (z >> 31)
    }

    /// Uniform integer in `[lo, hi]` inclusive (`lo <= hi` required).
    #[inline]
    pub fn range_i64(&mut self, lo: i64, hi: i64) -> i64 {
        debug_assert!(lo <= hi);
        let span = (hi - lo + 1) as u64;
        lo + (self.next_u64() % span) as i64
    }

    /// Uniform `usize` in `[lo, hi]` inclusive.
    #[inline]
    pub fn range_usize(&mut self, lo: usize, hi: usize) -> usize {
        debug_assert!(lo <= hi);
        let span = (hi - lo + 1) as u64;
        lo + (self.next_u64() % span) as usize
    }

    /// A deterministic `f64` in `[0, 1)`.
    #[inline]
    pub fn unit_f64(&mut self) -> f64 {
        // 53 significant bits → a uniform double in [0,1).
        (self.next_u64() >> 11) as f64 / (1u64 << 53) as f64
    }

    /// A deterministic price-like value in `[lo, hi)` rounded to cents.
    #[inline]
    pub fn money(&mut self, lo: f64, hi: f64) -> f64 {
        let v = lo + self.unit_f64() * (hi - lo);
        (v * 100.0).round() / 100.0
    }

    /// `true` with probability `p`.
    #[inline]
    pub fn chance(&mut self, p: f64) -> bool {
        self.unit_f64() < p
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    /// The sequence is fixed by the seed — reproducible across runs.
    #[test]
    fn deterministic_sequence() {
        let mut a = Rng::new(0xDEADBEEF);
        let mut b = Rng::new(0xDEADBEEF);
        for _ in 0..1000 {
            assert_eq!(a.next_u64(), b.next_u64());
        }
    }

    /// Different seeds diverge (a sanity check the seed actually threads in).
    #[test]
    fn distinct_seeds_diverge() {
        let mut a = Rng::new(1);
        let mut b = Rng::new(2);
        let diffs = (0..64).filter(|_| a.next_u64() != b.next_u64()).count();
        assert!(
            diffs > 60,
            "distinct seeds should mostly differ, got {diffs}/64"
        );
    }

    /// Ranges stay in bounds.
    #[test]
    fn ranges_are_bounded() {
        let mut r = Rng::new(42);
        for _ in 0..10_000 {
            let v = r.range_i64(5, 9);
            assert!((5..=9).contains(&v));
            let u = r.unit_f64();
            assert!((0.0..1.0).contains(&u));
        }
    }
}