statistical_comparison/
statistical_comparison.rs1use std::hash::{DefaultHasher, Hash};
15
16use consistent_choose_k::{ConsistentChooseKHasher, ConsistentPermutation};
17
18const SAMPLES: usize = 200_000;
19
20fn chi2_critical_999(df: usize) -> f64 {
25 let df = df as f64;
26 let a = 2.0 / (9.0 * df);
27 df * (1.0 - a + 3.0902 * a.sqrt()).powi(3)
28}
29
30fn chi2_uniform(observed: &[u64]) -> (f64, usize) {
33 let total: u64 = observed.iter().sum();
34 let cells = observed.len();
35 let expected = total as f64 / cells as f64;
36 let mut chi2 = 0.0;
37 for &c in observed {
38 let d = c as f64 - expected;
39 chi2 += d * d / expected;
40 }
41 (chi2, cells - 1)
42}
43
44fn chooseh_take(key: u64, n: usize, k: usize) -> Vec<u32> {
47 let mut h = DefaultHasher::default();
48 key.hash(&mut h);
49 ConsistentChooseKHasher::new(h, n)
50 .map(|v| v as u32)
51 .take(k)
52 .collect()
53}
54
55fn perm_take(key: u64, n: usize, k: usize) -> Vec<u32> {
56 ConsistentPermutation::new(n as u32, key).take(k).collect()
57}
58
59struct Acc {
62 name: String,
63 first: Vec<u64>,
64 kth: Vec<u64>,
65 pair: Vec<u64>, bits: Vec<Vec<u64>>, }
68
69impl Acc {
70 fn new(name: &str, n: usize, kk: usize, n_bits: usize) -> Self {
71 Self {
72 name: name.to_string(),
73 first: vec![0u64; n],
74 kth: vec![0u64; n],
75 pair: vec![0u64; n * n],
76 bits: vec![vec![0u64; n_bits]; kk],
77 }
78 }
79
80 fn record(&mut self, v: &[u32], n: usize, n_bits: usize) {
81 let kk = self.bits.len();
82 self.first[v[0] as usize] += 1;
83 self.kth[v[kk - 1] as usize] += 1;
84 let (lo, hi) = if v[0] <= v[1] {
85 (v[0], v[1])
86 } else {
87 (v[1], v[0])
88 };
89 self.pair[(lo as usize) * n + hi as usize] += 1;
90 for (pos, &val) in v.iter().enumerate().take(kk) {
91 for b in 0..n_bits {
92 if (val >> b) & 1 == 1 {
93 self.bits[pos][b] += 1;
94 }
95 }
96 }
97 }
98}
99
100fn run_for_n(n: usize) {
101 let kk = 2usize.min(n - 1).max(1);
102 let n_bits = ((n - 1).next_power_of_two().trailing_zeros() as usize).max(1);
103
104 type GenFn = Box<dyn Fn(u64, usize, usize) -> Vec<u32>>;
105
106 let methods: Vec<(&'static str, GenFn)> = vec![
108 ("ChooseKHasher ", Box::new(chooseh_take)),
109 ("Permutation ", Box::new(perm_take)),
110 ];
111
112 let mut accs: Vec<Acc> = methods
113 .iter()
114 .map(|(name, _)| Acc::new(name, n, kk, n_bits))
115 .collect();
116
117 for seed in 0..SAMPLES as u64 {
118 let mut z = seed.wrapping_add(0x9E37_79B9_7F4A_7C15);
124 z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
125 z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
126 let key = z ^ (z >> 31);
127 for ((_, gen), acc) in methods.iter().zip(accs.iter_mut()) {
128 let v = gen(key, n, kk);
129 assert_eq!(v.len(), kk);
130 acc.record(&v, n, n_bits);
131 }
132 }
133
134 println!("\n=== n = {n} (samples = {SAMPLES}) ===");
135 println!(
136 "{:<46} {:>14} {:>6} {:>14} {:>7}",
137 "test", "chi2", "df", "crit(0.001)", "verdict"
138 );
139
140 let print_row = |label: &str, chi2: f64, df: usize| {
141 let crit = chi2_critical_999(df);
142 let verdict = if chi2 <= crit { "PASS" } else { "FAIL" };
143 println!("{label:<46} {chi2:>14.2} {df:>6} {crit:>14.2} {verdict:>7}");
144 };
145
146 for acc in &accs {
148 let (c, d) = chi2_uniform(&acc.first);
149 print_row(&format!("{}: marginal @ pos 0", acc.name), c, d);
150 }
151 for acc in &accs {
153 let (c, d) = chi2_uniform(&acc.kth);
154 print_row(&format!("{}: marginal @ pos {}", acc.name, kk - 1), c, d);
155 }
156 for acc in &accs {
158 let mut cells = Vec::with_capacity(n * (n - 1) / 2);
159 for i in 0..n {
160 for j in (i + 1)..n {
161 cells.push(acc.pair[i * n + j]);
162 }
163 }
164 let (c, d) = chi2_uniform(&cells);
165 print_row(&format!("{}: choose-2 set uniformity", acc.name), c, d);
166 }
167 for acc in &accs {
169 let mut chi2 = 0.0;
170 let mut df = 0;
171 for b in 0..n_bits {
172 let pi = (0..n).filter(|v| (v >> b) & 1 == 1).count() as f64 / n as f64;
173 if pi == 0.0 || pi == 1.0 {
174 continue;
175 }
176 let exp_set = SAMPLES as f64 * pi;
177 let exp_unset = SAMPLES as f64 * (1.0 - pi);
178 for pos in 0..kk {
179 let set = acc.bits[pos][b] as f64;
180 let unset = SAMPLES as f64 - set;
181 chi2 += (set - exp_set).powi(2) / exp_set + (unset - exp_unset).powi(2) / exp_unset;
182 df += 1;
183 }
184 }
185 print_row(&format!("{}: per-(pos,bit) balance", acc.name), chi2, df);
186 }
187}
188
189fn main() {
190 println!("Statistical comparison of consistent-permutation generators");
191 println!("(Chi-squared tests, alpha = 0.001 — PASS means we cannot reject uniformity.)");
192 for n in [8usize, 16, 32, 64, 128, 256, 1024] {
193 run_for_n(n);
194 }
195}