ferray_random/bitgen/
pcg64.rs

1// ferray-random: PCG64 BitGenerator implementation
2//
3// PCG-XSL-RR 128/64 (LCG) from Melissa O'Neill's PCG paper.
4// Period: 2^128. No jump support.
5
6use super::BitGenerator;
7
8/// PCG64 (PCG-XSL-RR 128/64) pseudo-random number generator.
9///
10/// Uses a 128-bit linear congruential generator with a permutation-based
11/// output function. Period is 2^128. Does not support `jump()` or `stream()`.
12///
13/// # Example
14/// ```
15/// use ferray_random::bitgen::Pcg64;
16/// use ferray_random::bitgen::BitGenerator;
17///
18/// let mut rng = Pcg64::seed_from_u64(42);
19/// let val = rng.next_u64();
20/// ```
21pub struct Pcg64 {
22    state: u128,
23    inc: u128,
24}
25
26/// Default multiplier for the LCG (from PCG paper).
27const PCG_DEFAULT_MULTIPLIER: u128 = 0x2360_ED05_1FC6_5DA4_4385_DF64_9FCC_F645;
28
29impl Pcg64 {
30    /// Internal step function: advance the LCG state.
31    #[inline]
32    fn step(&mut self) {
33        self.state = self
34            .state
35            .wrapping_mul(PCG_DEFAULT_MULTIPLIER)
36            .wrapping_add(self.inc);
37    }
38
39    /// Output function: XSL-RR permutation of the 128-bit state to 64-bit output.
40    #[inline]
41    fn output(state: u128) -> u64 {
42        let xsl = ((state >> 64) ^ state) as u64;
43        let rot = (state >> 122) as u32;
44        xsl.rotate_right(rot)
45    }
46}
47
48impl BitGenerator for Pcg64 {
49    fn next_u64(&mut self) -> u64 {
50        let old_state = self.state;
51        self.step();
52        Self::output(old_state)
53    }
54
55    fn seed_from_u64(seed: u64) -> Self {
56        // Use SplitMix64-like expansion for seeding
57        let seed128 = {
58            let mut s = seed;
59            let a = splitmix64_step(&mut s);
60            let b = splitmix64_step(&mut s);
61            ((a as u128) << 64) | (b as u128)
62        };
63        // inc must be odd
64        let inc = {
65            let mut s = seed.wrapping_add(0xda3e39cb94b95bdb);
66            let a = splitmix64_step(&mut s);
67            let b = splitmix64_step(&mut s);
68            (((a as u128) << 64) | (b as u128)) | 1
69        };
70
71        let mut rng = Pcg64 { state: 0, inc };
72        rng.step();
73        rng.state = rng.state.wrapping_add(seed128);
74        rng.step();
75        rng
76    }
77
78    fn jump(&mut self) -> Option<()> {
79        // PCG64 does not support jump-ahead
80        None
81    }
82
83    fn stream(_seed: u64, _stream_id: u64) -> Option<Self> {
84        // PCG64 does not support stream IDs in this implementation
85        None
86    }
87}
88
89/// SplitMix64 step for seed expansion.
90fn splitmix64_step(state: &mut u64) -> u64 {
91    *state = state.wrapping_add(0x9e3779b97f4a7c15);
92    let mut z = *state;
93    z = (z ^ (z >> 30)).wrapping_mul(0xbf58476d1ce4e5b9);
94    z = (z ^ (z >> 27)).wrapping_mul(0x94d049bb133111eb);
95    z ^ (z >> 31)
96}
97
98impl Clone for Pcg64 {
99    fn clone(&self) -> Self {
100        Self {
101            state: self.state,
102            inc: self.inc,
103        }
104    }
105}
106
107#[cfg(test)]
108mod tests {
109    use super::*;
110
111    #[test]
112    fn deterministic_output() {
113        let mut rng1 = Pcg64::seed_from_u64(42);
114        let mut rng2 = Pcg64::seed_from_u64(42);
115        for _ in 0..1000 {
116            assert_eq!(rng1.next_u64(), rng2.next_u64());
117        }
118    }
119
120    #[test]
121    fn different_seeds_differ() {
122        let mut rng1 = Pcg64::seed_from_u64(42);
123        let mut rng2 = Pcg64::seed_from_u64(43);
124        let mut same = true;
125        for _ in 0..100 {
126            if rng1.next_u64() != rng2.next_u64() {
127                same = false;
128                break;
129            }
130        }
131        assert!(!same);
132    }
133
134    #[test]
135    fn jump_not_supported() {
136        let mut rng = Pcg64::seed_from_u64(42);
137        assert!(rng.jump().is_none());
138    }
139
140    #[test]
141    fn stream_not_supported() {
142        assert!(Pcg64::stream(42, 0).is_none());
143    }
144
145    #[test]
146    fn output_covers_full_range() {
147        let mut rng = Pcg64::seed_from_u64(12345);
148        let mut seen_high = false;
149        let mut seen_low = false;
150        for _ in 0..10_000 {
151            let v = rng.next_u64();
152            if v > (u64::MAX / 2) {
153                seen_high = true;
154            } else {
155                seen_low = true;
156            }
157            if seen_high && seen_low {
158                break;
159            }
160        }
161        assert!(seen_high && seen_low);
162    }
163}
ferray_random/bitgen/pcg64.rs

ferray_random/bitgen/
pcg64.rs
