#[derive(Clone, Debug)]
pub struct Rng {
state: u64,
}
impl Rng {
pub fn new(seed: u64) -> Self {
Rng { state: seed }
}
pub fn derive(&self, stream: u64) -> Rng {
Rng::new(mix(self.state ^ mix(stream.wrapping_add(GOLDEN_GAMMA))))
}
pub fn next_u64(&mut self) -> u64 {
self.state = self.state.wrapping_add(GOLDEN_GAMMA);
mix(self.state)
}
pub fn next_f64(&mut self) -> f64 {
unit(self.next_u64())
}
pub fn below(&mut self, n: usize) -> usize {
assert!(n > 0, "cannot draw from an empty range");
((self.next_u64() as u128 * n as u128) >> 64) as usize
}
pub fn sample_distinct(&mut self, n: usize, out: &mut [usize]) {
assert!(out.len() <= n, "cannot draw {} distinct of {n}", out.len());
for i in 0..out.len() {
out[i] = loop {
let candidate = self.below(n);
if !out[..i].contains(&candidate) {
break candidate;
}
};
}
}
}
pub fn hash3(a: u64, b: u64, c: u64) -> u64 {
mix(mix(mix(a.wrapping_add(GOLDEN_GAMMA)).wrapping_add(b)).wrapping_add(c))
}
pub fn unit(bits: u64) -> f64 {
(bits >> 11) as f64 * (1.0 / (1u64 << 53) as f64)
}
const GOLDEN_GAMMA: u64 = 0x9E37_79B9_7F4A_7C15;
fn mix(mut z: u64) -> u64 {
z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
z ^ (z >> 31)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn matches_the_reference_splitmix64_sequence() {
let mut rng = Rng::new(0);
assert_eq!(rng.next_u64(), 0xE220_A839_7B1D_CDAF);
}
#[test]
fn is_deterministic_and_streams_are_independent() {
let root = Rng::new(42);
let draw = |mut r: Rng| (0..8).map(|_| r.next_u64()).collect::<Vec<_>>();
assert_eq!(draw(root.derive(1)), draw(root.derive(1)));
assert_ne!(draw(root.derive(1)), draw(root.derive(2)));
assert_ne!(draw(root.derive(0)), draw(root.clone()));
}
#[test]
fn draws_stay_in_range() {
let mut rng = Rng::new(7);
for _ in 0..10_000 {
let f = rng.next_f64();
assert!((0.0..1.0).contains(&f));
assert!(rng.below(13) < 13);
}
}
#[test]
fn samples_are_distinct() {
let mut rng = Rng::new(9);
let mut sample = [0usize; 8];
for _ in 0..1000 {
rng.sample_distinct(10, &mut sample);
let mut sorted = sample;
sorted.sort_unstable();
assert!(sorted.windows(2).all(|w| w[0] < w[1]));
assert!(sorted[7] < 10);
}
}
}