gen_hll_bias_nx.nx source
↩ module page · 199 lines · 6247 B
1// gen_hll_bias_nx.nx -- generate HLL bias table by running OUR HLL.
2//
3// SOVEREIGN-SUBSTRATE DISCIPLINE: prior generator used Python's
4// getrandbits(64) and Python's idealized HLL math. That calibrated
5// the bias table to PYTHON, not to our actual murmur3-based HLL.
6// This generator runs OUR HLL on synthetic streams, collecting the
7// raw alpha*m^2/sum_q32 directly from our register array.
8//
9// Output: writes hll_bias_table.nx-compatible const block to stdout.
10// Caller redirects to runtime/hll_bias_table.nx.
11//
12// Caller args (compile-time consts here -- substrate has no argv yet):
13// lg_k_min, lg_k_max -- range of lg_k to generate tables for
14// n_samples -- sample points per lg_k across (threshold, 5m]
15// n_seeds -- HLL trials per sample point
16
17import "syscalls.nx"
18import "sketch_hll.nx"
19
20const NX_GEN_LG_K_MIN: i64 = 4
21const NX_GEN_LG_K_MAX: i64 = 10
22// 192 samples per lg_k (3x prior density of 64) for tighter cubic
23// Lagrange interpolation. DS canonical xArrs uses 257; we match
24// roughly but stay slightly lower to keep generation time reasonable.
25const NX_GEN_N_SAMPLES: i64 = 192
26// Seeds per sample. Each sample's reported raw_est is the mean over
27// this many HLL trials. Sample stderr ~ raw_est * (1.04/sqrt(m)) / sqrt(n_seeds).
28// For lg_k=7 (1.04/sqrt(128) ≈ 9.2%), 500 seeds gives stderr ~ 0.4% of raw_est.
29const NX_GEN_N_SEEDS: i64 = 500
30// Upper-N multiplier on m. Prior 5*m left a "blind spot" between
31// 5m and the asymptotic-bias-free zone (~10m+). Extend to 10m to
32// cover that overlap.
33const NX_GEN_UPPER_MULT: i64 = 10
34
35// === decimal emitter (i64 -> stdout) ============================
36
37func gn_putc(c: i64) -> i64 {
38 let buf: *u8 = sys_mmap(1)
39 buf[0] = c & 0xFF
40 sys_write(1, buf, 1)
41 return 0
42}
43
44func gn_str(s: *u8, len: i64) -> i64 {
45 sys_write(1, s, len)
46 return 0
47}
48
49func gn_i64(n: i64) -> i64 {
50 if n < 0 {
51 gn_putc(45)
52 return gn_i64(-n)
53 }
54 if n == 0 {
55 gn_putc(48)
56 return 0
57 }
58 let digits: *u8 = sys_mmap(32)
59 var d: i64 = 0
60 var v: i64 = n
61 while v > 0 {
62 digits[d] = (v % 10) + 48
63 v = v / 10
64 d = d + 1
65 }
66 while d > 0 {
67 d = d - 1
68 gn_putc(digits[d])
69 }
70 return 0
71}
72
73func gn_nl() -> i64 {
74 gn_putc(10)
75 return 0
76}
77
78// === RAW HLL estimate -- bypasses LC and bias-correction =========
79//
80// Returns alpha_m * m^2 / sum_q32 (the pre-correction value), so the
81// caller can use it as the X axis in the bias table.
82
83func nx_hll_raw_estimate(h: *Hll) -> i64 {
84 let m: i64 = h.m
85 var sum_q32: i64 = 0
86 var i: i64 = 0
87 while i < m {
88 let r: i64 = h.regs[i]
89 sum_q32 = sum_q32 + nx_hll_pow2_neg_q32(r)
90 i = i + 1
91 }
92 if sum_q32 == 0 { return m }
93 let alpha_m_sq_q64: i64 = nx_hll_alpha_m_sq_q64(h.lg_k)
94 if alpha_m_sq_q64 == 0 { return 0 }
95 return alpha_m_sq_q64 / sum_q32
96}
97
98// === main =======================================================
99
100func main() -> i64 {
101 gn_str("// hll_bias_table.nx -- bias table calibrated by OUR HLL on OUR streams.", 71)
102 gn_nl()
103 gn_str("// Generated by runtime/gen_hll_bias_nx.nx via qemu-riscv64-static.", 65)
104 gn_nl()
105 gn_str("// genealogy_id: heule_2013 + ours (substrate-native generation)", 63)
106 gn_nl()
107 gn_str("// lineage_id: heule_bias_table", 31)
108 gn_nl()
109 gn_nl()
110
111 let buf: *u8 = sys_mmap(8)
112 var lg_k: i64 = NX_GEN_LG_K_MIN
113 while lg_k <= NX_GEN_LG_K_MAX {
114 let m: i64 = 1 << lg_k
115 let thresh: i64 = nx_hll_heule_threshold(lg_k)
116 let upper: i64 = NX_GEN_UPPER_MULT * m
117 let n_samp: i64 = NX_GEN_N_SAMPLES
118
119 gn_str("// lg_k=", 8)
120 gn_i64(lg_k)
121 gn_str(" m=", 3)
122 gn_i64(m)
123 gn_str(" threshold=", 11)
124 gn_i64(thresh)
125 gn_str(" upper=", 7)
126 gn_i64(upper)
127 gn_str(" n_samples=", 11)
128 gn_i64(n_samp)
129 gn_nl()
130
131 gn_str("const NX_HLL_BIAS_LGK", 21)
132 gn_i64(lg_k)
133 gn_str("_N: i64 = ", 10)
134 gn_i64(n_samp)
135 gn_nl()
136
137 gn_str("func nx_hll_bias_lgk", 20)
138 gn_i64(lg_k)
139 gn_str("(i: i64) -> i64 {", 17)
140 gn_nl()
141
142 var s: i64 = 0
143 while s < n_samp {
144 // sample N evenly across (threshold, upper]
145 let n_target: i64 = thresh + ((upper - thresh) * (s + 1)) / (n_samp + 1)
146
147 // Average raw_est over N_SEEDS trials with different streams.
148 var sum_raw: i64 = 0
149 var seed_idx: i64 = 0
150 while seed_idx < NX_GEN_N_SEEDS {
151 let workload_seed: i64 = seed_idx + 1
152 let hll: *Hll = nx_hll_alloc(lg_k, 42)
153 var ki: i64 = 0
154 while ki < n_target {
155 let k: i64 = workload_seed * 100000 + ki
156 buf[0] = (k ) & 0xFF
157 buf[1] = (k >> 8 ) & 0xFF
158 buf[2] = (k >> 16) & 0xFF
159 buf[3] = (k >> 24) & 0xFF
160 buf[4] = 0
161 buf[5] = 0
162 buf[6] = 0
163 buf[7] = 0
164 nx_hll_add(hll, buf, 8)
165 ki = ki + 1
166 }
167 sum_raw = sum_raw + nx_hll_raw_estimate(hll)
168 seed_idx = seed_idx + 1
169 }
170 let mean_raw: i64 = sum_raw / NX_GEN_N_SEEDS
171
172 // emit one (raw, n) pair as two if-equalities (matches function table format)
173 gn_str(" if i == ", 12)
174 gn_i64(s * 2)
175 gn_str(" { return ", 11)
176 gn_i64(mean_raw)
177 gn_str(" }", 2)
178 gn_nl()
179 gn_str(" if i == ", 12)
180 gn_i64(s * 2 + 1)
181 gn_str(" { return ", 11)
182 gn_i64(n_target)
183 gn_str(" }", 2)
184 gn_nl()
185
186 s = s + 1
187 }
188
189 gn_str(" return -1", 13)
190 gn_nl()
191 gn_str("}", 1)
192 gn_nl()
193 gn_nl()
194
195 lg_k = lg_k + 1
196 }
197
198 return 0
199}