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 expansion for seeding (#259 — shared helper).
57        let seed128 = {
58            let mut s = seed;
59            let a = super::splitmix64(&mut s);
60            let b = super::splitmix64(&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 = super::splitmix64(&mut s);
67            let b = super::splitmix64(&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
89impl Clone for Pcg64 {
90    fn clone(&self) -> Self {
91        Self {
92            state: self.state,
93            inc: self.inc,
94        }
95    }
96}
97
98#[cfg(test)]
99mod tests {
100    use super::*;
101
102    #[test]
103    fn deterministic_output() {
104        let mut rng1 = Pcg64::seed_from_u64(42);
105        let mut rng2 = Pcg64::seed_from_u64(42);
106        for _ in 0..1000 {
107            assert_eq!(rng1.next_u64(), rng2.next_u64());
108        }
109    }
110
111    #[test]
112    fn different_seeds_differ() {
113        let mut rng1 = Pcg64::seed_from_u64(42);
114        let mut rng2 = Pcg64::seed_from_u64(43);
115        let mut same = true;
116        for _ in 0..100 {
117            if rng1.next_u64() != rng2.next_u64() {
118                same = false;
119                break;
120            }
121        }
122        assert!(!same);
123    }
124
125    #[test]
126    fn jump_not_supported() {
127        let mut rng = Pcg64::seed_from_u64(42);
128        assert!(rng.jump().is_none());
129    }
130
131    #[test]
132    fn stream_not_supported() {
133        assert!(Pcg64::stream(42, 0).is_none());
134    }
135
136    #[test]
137    fn output_covers_full_range() {
138        let mut rng = Pcg64::seed_from_u64(12345);
139        let mut seen_high = false;
140        let mut seen_low = false;
141        for _ in 0..10_000 {
142            let v = rng.next_u64();
143            if v > (u64::MAX / 2) {
144                seen_high = true;
145            } else {
146                seen_low = true;
147            }
148            if seen_high && seen_low {
149                break;
150            }
151        }
152        assert!(seen_high && seen_low);
153    }
154}
ferray_random/bitgen/pcg64.rs

ferray_random/bitgen/
pcg64.rs
