Skip to main content

openqmc/
rank1.rs

1//! Port of `oqmc/rank1.h` — a rank-1 lattice (Hickernell et al., "Weighted
2//! Compound Integration Rules with Higher Order Convergence for all N") made
3//! progressive with a radical inversion of the sample index, randomised with
4//! toroidal shifts.
5
6use crate::pcg;
7use crate::permute::reverse_and_shuffle;
8
9/// Generator vector from the Hickernell et al. publication.
10const LATTICE: [u32; 4] = [1, 364981, 245389, 97823];
11
12/// Toroidal shift: offset a value, relying on integer wraparound.
13#[inline]
14const fn rotate(value: u32, distance: u32) -> u32 {
15    value.wrapping_add(distance)
16}
17
18/// Rank-1 lattice value at a bit-reversed index for a given dimension (0..4).
19#[inline]
20pub const fn lattice_reversed_index(index: u32, dimension: usize) -> u32 {
21    debug_assert!(dimension <= 3);
22    LATTICE[dimension].wrapping_mul(index)
23}
24
25/// Compute a randomised rank-1 lattice value.
26///
27/// `DEPTH` is the dimensional output count (1..=4). `pattern_id` seeds the
28/// randomisation and must be constant for a given lattice.
29#[inline]
30pub fn shuffled_rotated_lattice<const DEPTH: usize>(
31    index: u32,
32    mut pattern_id: u32,
33) -> [u32; DEPTH] {
34    const {
35        assert!(
36            DEPTH >= 1 && DEPTH <= 4,
37            "Pattern depth must be within [1, 4]"
38        )
39    };
40
41    let index = reverse_and_shuffle(index, pcg::output(pattern_id));
42
43    let mut sample = [0u32; DEPTH];
44    let mut i = 0;
45    while i < DEPTH {
46        // pcg::rng advances `pattern_id` and returns a fresh shift each iteration.
47        sample[i] = rotate(lattice_reversed_index(index, i), pcg::rng(&mut pattern_id));
48        i += 1;
49    }
50    sample
51}
52
53#[cfg(test)]
54mod tests {
55    use super::*;
56
57    #[test]
58    fn deterministic() {
59        let a = shuffled_rotated_lattice::<4>(7, pcg::hash(3));
60        let b = shuffled_rotated_lattice::<4>(7, pcg::hash(3));
61        assert_eq!(a, b);
62    }
63
64    #[test]
65    fn dimension0_generator_is_one() {
66        // LATTICE[0] == 1, so dim0 is a pure radical-inverse + shift.
67        assert_eq!(lattice_reversed_index(12345, 0), 12345);
68    }
69
70    #[test]
71    fn generator_vector_matches_the_publication() {
72        assert_eq!(LATTICE, [1, 364981, 245389, 97823]);
73    }
74
75    #[test]
76    fn generator_components_are_odd_and_distinct() {
77        for (d, &g) in LATTICE.iter().enumerate() {
78            assert_eq!(g & 1, 1, "dim {d}");
79        }
80        let mut sorted = LATTICE;
81        sorted.sort_unstable();
82        for w in sorted.windows(2) {
83            assert_ne!(w[0], w[1]);
84        }
85    }
86
87    #[test]
88    fn toroidal_rotate_is_wrapping_addition() {
89        assert_eq!(rotate(u32::MAX, 1), 0);
90        assert_eq!(rotate(0, 0), 0);
91        assert_eq!(rotate(5, 7), 12);
92        assert_eq!(rotate(0x8000_0000, 0x8000_0000), 0);
93    }
94
95    #[test]
96    fn reversed_index_is_generator_times_index() {
97        for (d, &g) in LATTICE.iter().enumerate() {
98            for i in [0u32, 1, 2, 12345, u32::MAX] {
99                assert_eq!(lattice_reversed_index(i, d), g.wrapping_mul(i));
100            }
101        }
102    }
103
104    #[test]
105    fn shuffled_seeds_the_shuffle_with_output_and_the_shifts_with_rng() {
106        let pattern = pcg::hash(9);
107        for index in [0u32, 1, 77, 65535] {
108            let r = reverse_and_shuffle(index, pcg::output(pattern));
109            let mut state = pattern;
110            let expected: [u32; 4] =
111                std::array::from_fn(|d| rotate(lattice_reversed_index(r, d), pcg::rng(&mut state)));
112            assert_eq!(shuffled_rotated_lattice::<4>(index, pattern), expected);
113        }
114    }
115
116    #[test]
117    fn depth_prefixes_agree() {
118        let p = pcg::hash(4);
119        let four = shuffled_rotated_lattice::<4>(11, p);
120        assert_eq!(&four[..2], &shuffled_rotated_lattice::<2>(11, p)[..]);
121        assert_eq!(&four[..1], &shuffled_rotated_lattice::<1>(11, p)[..]);
122    }
123
124    #[test]
125    fn each_dimension_is_stratified_over_a_prefix() {
126        let p = pcg::hash(8);
127        for m in 1..=10u32 {
128            for d in 0..4 {
129                let mut seen = vec![false; 1 << m];
130                for i in 0..(1u32 << m) {
131                    let cell = (shuffled_rotated_lattice::<4>(i, p)[d] >> (32 - m)) as usize;
132                    assert!(!seen[cell], "m={m} d={d}");
133                    seen[cell] = true;
134                }
135            }
136        }
137    }
138}