competitive_library/other/
xorshift.rs

1//! Xorshift random number generator
2use std::{
3    fmt::{Debug, Display},
4    time::SystemTime,
5};
6
7#[derive(Clone, Default, Copy, Debug)]
8pub struct XorShift<T>
9where
10    T: std::fmt::Debug + Sized + Copy + Display + Shift,
11{
12    seed: T,
13}
14
15impl<T> XorShift<T>
16where
17    T: std::fmt::Debug + Sized + Copy + Display + Shift,
18{
19    pub fn new() -> Self {
20        XorShift::from_seed(T::seed())
21    }
22    pub fn from_seed(seed: T) -> XorShift<T> {
23        XorShift { seed }
24    }
25}
26
27impl<T> Iterator for XorShift<T>
28where
29    T: std::fmt::Debug + Sized + Copy + Display + Shift,
30{
31    type Item = T;
32
33    fn next(&mut self) -> Option<Self::Item> {
34        T::shift(&mut self.seed);
35        Some(self.seed)
36    }
37}
38
39pub trait Shift {
40    fn seed() -> Self;
41    fn shift(n: &mut Self);
42}
43
44impl Shift for u64 {
45    fn seed() -> Self {
46        SystemTime::now()
47            .duration_since(SystemTime::UNIX_EPOCH)
48            .unwrap()
49            .as_secs()
50    }
51
52    fn shift(state: &mut u64) {
53        *state ^= *state << 13;
54        *state ^= *state >> 7;
55        *state ^= *state << 17;
56    }
57}
58impl Shift for u32 {
59    fn seed() -> Self {
60        SystemTime::now()
61            .duration_since(SystemTime::UNIX_EPOCH)
62            .unwrap()
63            .as_secs() as u32
64    }
65
66    fn shift(state: &mut u32) {
67        *state ^= *state << 13;
68        *state ^= *state >> 17;
69        *state ^= *state << 5;
70    }
71}
72
73#[cfg(test)]
74mod tests {
75    use super::*;
76    use std::collections::HashSet;
77    #[test]
78    fn test_xorshift() {
79        let mut set = HashSet::new();
80        let xorshift = XorShift::<u64>::new();
81
82        for v in xorshift.take(100_000) {
83            assert!(!set.contains(&v));
84            set.insert(v);
85        }
86    }
87}
competitive_library/other/xorshift.rs

competitive_library/other/
xorshift.rs
