atcoder/lib/
random.rs

1//! 外部 crate を使わない軽量な疑似乱数生成器です。
2
3/// Xorshift による64 bit疑似乱数生成器です。
4///
5/// 競技中のランダムテストやヒューリスティック用途を想定しています。暗号用途には適しません。
6/// 内部状態を更新する各生成操作は `O(1)` で、同じ seed からは同じ列を生成します。
7///
8/// # Examples
9///
10/// ```
11/// use atcoder::random::Xorshift;
12///
13/// let mut rng = Xorshift::new(7);
14/// let value = rng.range_inclusive(1, 6);
15/// assert!((1..=6).contains(&value));
16/// ```
17#[derive(Debug, Clone)]
18pub struct Xorshift {
19    state: u64,
20}
21
22impl Xorshift {
23    /// `seed` を初期状態として生成器を作ります。
24    ///
25    /// `seed == 0` の場合は固定の非ゼロ値へ置き換えます。同じ seed から作った生成器は同じ値列を生成します。
26    pub const fn new(seed: u64) -> Self {
27        Self {
28            state: if seed == 0 {
29                88_172_645_463_325_252
30            } else {
31                seed
32            },
33        }
34    }
35
36    /// Xorshift 更新を1回行い、次の `u64` を返します。
37    pub fn next_u64(&mut self) -> u64 {
38        self.state ^= self.state << 13;
39        self.state ^= self.state >> 7;
40        self.state ^= self.state << 17;
41        self.state
42    }
43
44    /// [`next_u64`](Self::next_u64) を呼び出し、次の `u64` を返します。
45    ///
46    /// [`next_u64`](Self::next_u64) と同じです。
47    #[allow(clippy::should_implement_trait)]
48    pub fn next(&mut self) -> u64 {
49        self.next_u64()
50    }
51
52    /// 閉区間 `[min, max]` から疑似乱数の `usize` を返します。
53    ///
54    /// `min > max` の場合と、区間幅が `usize` で表せない場合は panic します。剰余による
55    /// ごく小さな偏りがあるため、厳密な一様分布が必要な用途には適しません。特に `0..=usize::MAX`
56    /// は幅が `usize` に収まらないため panic します。
57    pub fn range_inclusive(&mut self, min: usize, max: usize) -> usize {
58        assert!(min <= max, "empty range");
59        let width = max.checked_sub(min).unwrap().checked_add(1).unwrap();
60        min + self.next_u64() as usize % width
61    }
62
63    /// 閉区間 `[min, max]` から疑似乱数の `usize` を返します。
64    ///
65    /// [`range_inclusive`](Self::range_inclusive) と同じです。
66    pub fn next_range(&mut self, min: usize, max: usize) -> usize {
67        self.range_inclusive(min, max)
68    }
69
70    /// 半開区間 `[0.0, 1.0)` の `f64` を返します。
71    ///
72    /// 上位53ビットを使って値を作ります。値が等確率になる暗号学的乱数ではありません。
73    pub fn next_f64(&mut self) -> f64 {
74        const SCALE: f64 = (1_u64 << 53) as f64;
75        (self.next_u64() >> 11) as f64 / SCALE
76    }
77}
78
79#[cfg(test)]
80mod tests {
81    use super::Xorshift;
82
83    #[test]
84    fn is_deterministic_and_bounded() {
85        let mut left = Xorshift::new(1);
86        let mut right = Xorshift::new(1);
87        assert_eq!(left.next_u64(), right.next_u64());
88        assert!((3..=7).contains(&left.range_inclusive(3, 7)));
89        assert!((0.0..1.0).contains(&left.next_f64()));
90    }
91}
atcoder/lib/random.rs

atcoder/lib/
random.rs
