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