nx_sketch_hll.nx source

1// sketch_hll.nx -- HyperLogLog cardinality sketch in NishiLang. 2// 3// Flajolet 2007 + Heule 2013 small-range correction. Sovereign- 4// tier sibling port of nishi-engine/packages/core-sketch/src/hll.ts. 5// All-i64 implementation: no f64 source-level types, no float 6// literals; harmonic-mean estimator computed in Q32.32 fixed-point 7// so the file compiles through both the C-anchor (Wheeler comparator) 8// and the NishiLang sibling. 9// 10// Per the lossless-language meta-cardinal (nishi-engine doc 20): 11// the cardinality estimate ships in an Approximate<i64> envelope 12// declaring stddev_rel = 1.04/sqrt(m) at confidence 0.6827, with 13// MaturityClass = ReferenceImpl and AdversarialSafety = Honest. 14// Bounded-loss-by-typing, not silent-loss. 15// 16// Memory: 1 byte per register. lgK=11 -> 2048 bytes; lgK=12 -> 17// 4096 bytes. Standard error: 1.04 / sqrt(2^lgK). 18// 19// Roadmap citations: 20// doc 19 -- DataSketches stomp roadmap 21// doc 20 -- universal lossless language 22// doc 21 -- research partnership not isolation 23 24// nx_safety_envelope: 25// intended_use: AUTO_APPLIED -- primitive-specific tuning queued 26// sil_target: SIL1 27// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail] 28// verdict: NOT_YET_EVALUATED 29 30import "nx_syscalls.nx" 31import "nx_murmur3.nx" 32import "nx_xxhash.nx" 33import "nx_bit.nx" 34import "nx_bits.nx" 35import "nx_sketch_types.nx" 36import "nx_hll_bias_table.nx" 37import "nx_i128.nx" 38 39// lgK in [4, 10] keeps alpha_m_sq * 2^32 comfortably in signed i64 40// (max signed i64 ~9.22e18; lgK=10 puts us at ~3.23e18). lgK >= 11 41// would overflow with this Q32.32 scaling; queued for a v2 estimator 42// that uses a narrower fixed-point format (e.g. Q16.48) for the 43// upper precision range. Practical sketches today use lgK 7-10 44// (1.04/sqrt(m): 9.2% to 3.3% rel-stddev). 45const NX_HLL_LGK_MIN: i64 = 4 46const NX_HLL_LGK_MAX: i64 = 10 47 48// Murmur3 seed-mixing constants. Source: original murmur3 paper 49// (Appleby 2008) for hash-family de-correlation. Same values used by 50// DataSketches (apache/datasketches-java HllUtil.java). 51const NX_HLL_SEED_HI: i64 = 0x9747B28C 52const NX_HLL_SEED_LO: i64 = 0x36185EC0 53 54// Math constants used in the LC formula. Each named with its source. 55// ln(2) ≈ 0.693147180559945... -- math constant (lineage: log_function) 56// PPM_SCALE = 1_000_000 -- our fixed-point scale (1e6 = "parts per million") 57// We keep ln(2) at micro-precision (PPM); going finer needs a wider 58// intermediate (Q32+) which we defer to v2. 59const NX_HLL_PPM_SCALE: i64 = 1000000 60const NX_HLL_LN2_PPM: i64 = 693147 // ln(2) * 1e6 61 62// DS composite-estimator LC peg. Used to smooth the LC -> bias-corrected 63// transition: if bias_corrected_est <= (LC_PEG_NUM / LC_PEG_DEN) * K, the 64// estimator takes min(bias_corrected, linear_counting). Source: 65// DataSketches HllUtil 0.7 constant; rationale per Heule 2013 §4. 66const NX_HLL_LC_PEG_NUM: i64 = 7 67const NX_HLL_LC_PEG_DEN: i64 = 10 68 69// HLL handle. 24 bytes. regs is a separately-allocated m-byte 70// register array. 71struct Hll { 72 regs: *u8, 73 lg_k: i64, 74 m: i64, 75 seed: i64, 76} 77 78// === leading-zero helpers ========================================== 79// 80// Standard binary-search count-leading-zeros for a 32-bit value 81// (input must be in low 32 bits of an i64). Used for rho. 82 83// Delegated to nx_bits_clz32 (dispatches to bsr+xor / clzw intrinsic). 84// One machine instruction in the HLL rho path. 85// nx_clz32 is NOT redefined here. It is owned by nx_bit.nx (imported above, line 33), 86// which carries the identical `return nx_bits_clz32(x)` delegation. This file used to 87// define its own copy, so every consumer importing nx_sketch_hll.nx held TWO definitions 88// of nx_clz32 -- accepted silently by nx_cc until the duplicate-definition guard 89// (debt 1785447657) made it fail closed. Removed 2026-07-31. 90 91// === construction ================================================= 92 93func nx_hll_alloc(lg_k: i64, seed: i64) -> *Hll { 94 if lg_k < NX_HLL_LGK_MIN { return 0 as *Hll } 95 if lg_k > NX_HLL_LGK_MAX { return 0 as *Hll } 96 let m: i64 = 1 << lg_k 97 let raw: *u8 = sys_mmap(24) 98 let h: *Hll = raw as *Hll 99 h.regs = sys_mmap(m) 100 h.lg_k = lg_k 101 h.m = m 102 h.seed = seed 103 var i: i64 = 0 104 while i < m { 105 h.regs[i] = 0 106 i = i + 1 107 } 108 return h 109} 110 111// === add =========================================================== 112// 113// Hash via 2x murmur3_32 with derived seeds (legacy path) -- gives a 114// 64-bit hash domain spliced from two 32-bit murmur3 outputs. Top 115// lg_k bits of hi = bucket index; suffix-then-lo drives rho. 116// 117// 2026-05-10 SELF-REMEDIATION TRACE (worked example for the 118// SELF_REMEDIATION_AS_MATHEMATICIAN cardinal): 119// Hypothesis: swap to xxh64 (single 64-bit, SMHasher-passing) 120// would tighten small-N accuracy without regressing high-N. 121// Phase 5 A/B: small-N tightened (n=100/200 became TIES vs DS) 122// BUT n=2000 regressed (mean 108 -> 142, lost BEATS). 123// Phase 6 generalization proof: REGRESSED at n=2000 cell. 124// Verdict: swap rejected. REVERTED to 2x murmur3_32. 125// 126// Root cause hypothesis (deferred until proper diagnosis): 127// xxh64 and 2x murmur3_32 both pass SMHasher. Difference at high 128// N is in higher-moment behavior that SMHasher's chi-squared 129// doesn't capture, or in alpha_m_sq_q64 calibration that has 130// subtle dependence on hash family's 4th-moment behavior. Queued 131// IMPROVEMENT_OPP: instrument register-distribution histograms 132// per hash family + per N to identify which moment diverges. 133// 134// genealogy_id: appleby_murmur3 (Austin Appleby) 135func nx_hll_add(h: *Hll, key: *u8, len: i64) -> i64 { 136 let seed_hi: i64 = h.seed ^ NX_HLL_SEED_HI 137 let seed_lo: i64 = h.seed ^ NX_HLL_SEED_LO 138 let hi: i64 = murmur3_32(seed_hi, key, len) & 0xFFFFFFFF 139 let lo: i64 = murmur3_32(seed_lo, key, len) & 0xFFFFFFFF 140 141 let idx: i64 = hi >> (32 - h.lg_k) 142 143 let upper: i64 = (hi << h.lg_k) & 0xFFFFFFFF 144 var r: i64 = 0 145 if upper != 0 { 146 r = nx_clz32(upper) + 1 147 } 148 if upper == 0 { 149 if lo != 0 { 150 r = (32 - h.lg_k) + nx_clz32(lo) + 1 151 } 152 if lo == 0 { 153 r = (64 - h.lg_k) + 1 154 } 155 } 156 157 if r > 255 { r = 255 } 158 159 let cur: i64 = h.regs[idx] 160 if cur < r { 161 h.regs[idx] = r 162 } 163 return 0 164} 165 166// === estimate (Q32.32 fixed-point harmonic mean) =================== 167// 168// E_raw = alpha_m * m^2 / sum(2^-r_j) 169// Stored as Q32.32: alpha_m_sq_q64 = alpha_m * m^2 * 2^32. 170// sum_q32 = sum_j ((1 << 32) >> r_j) (with 0 for r_j > 32) 171// estimate = alpha_m_sq_q64 / sum_q32 (i64 cardinality) 172// 173// alpha_m for lg_k >= 7 uses Flajolet's continuous approximation: 174// alpha_m = 0.7213 / (1 + 1.079 / m) 175// Lower lg_k uses tabulated values: 16->0.673, 32->0.697, 64->0.709. 176// 177// Hardcoded alpha_m_sq_q64 for lg_k in [4, 15]; computed offline 178// to avoid any floating-point operation in the hot path. 179 180// BUG FIX 2026-05-12: prior values were 877-995x too large, giving 1000x 181// over-estimates at n >> m where the classical HLL formula kicks in. 182// Smoke gates never caught this because they only exercised small-N where 183// the linear-counting correction takes over. Verified against DataSketches 184// Python 5.2.0 on n=1000 workload (was 1,137,371; should be ~1000). 185// 186// Correct formula: alpha_m * m^2 * 2^32 where alpha_m per Heule 2013: 187// m=16: alpha = 0.673 188// m=32: alpha = 0.697 189// m=64: alpha = 0.709 190// m>=128: alpha = 0.7213 / (1 + 1.079/m) 191func nx_hll_alpha_m_sq_q64(lg_k: i64) -> i64 { 192 if lg_k == 4 { return 739971325493 } // 0.673 * 16^2 * 2^32 193 if lg_k == 5 { return 3065438418239 } // 0.697 * 32^2 * 2^32 194 if lg_k == 6 { return 12472859905490 } // 0.709 * 64^2 * 2^32 195 if lg_k == 7 { return 50332686358312 } // alpha_128 * 128^2 * 2^32 196 if lg_k == 8 { return 202175761456818 } // alpha_256 * 256^2 * 2^32 197 if lg_k == 9 { return 810403740235830 } // alpha_512 * 512^2 * 2^32 198 if lg_k == 10 { return 3245027090684401 } // alpha_1024 * 1024^2 * 2^32 199 return 0 200} 201 202func nx_hll_pow2_neg_q32(r: i64) -> i64 { 203 if r >= 32 { return 0 } 204 if r <= 0 { return 1 << 32 } 205 return (1 << 32) >> r 206} 207 208// Per-lg_k thresholds for the LC-vs-classical-HLL switch. 209// Source: Heule 2013 supplementary tables (genealogy_id: heule_2013; 210// lineage_id: heule_bias_table). Each value is the maximum cardinality 211// at which the linear-counting formula is more accurate than raw HLL 212// for that lg_k. Below the threshold: use LC. Above: use raw HLL. 213const NX_HLL_HEULE_THRESH_LGK4: i64 = 10 214const NX_HLL_HEULE_THRESH_LGK5: i64 = 20 215const NX_HLL_HEULE_THRESH_LGK6: i64 = 40 216const NX_HLL_HEULE_THRESH_LGK7: i64 = 80 217const NX_HLL_HEULE_THRESH_LGK8: i64 = 220 218const NX_HLL_HEULE_THRESH_LGK9: i64 = 400 219const NX_HLL_HEULE_THRESH_LGK10: i64 = 900 220 221func nx_hll_heule_threshold(lg_k: i64) -> i64 { 222 if lg_k == 4 { return NX_HLL_HEULE_THRESH_LGK4 } 223 if lg_k == 5 { return NX_HLL_HEULE_THRESH_LGK5 } 224 if lg_k == 6 { return NX_HLL_HEULE_THRESH_LGK6 } 225 if lg_k == 7 { return NX_HLL_HEULE_THRESH_LGK7 } 226 if lg_k == 8 { return NX_HLL_HEULE_THRESH_LGK8 } 227 if lg_k == 9 { return NX_HLL_HEULE_THRESH_LGK9 } 228 if lg_k == 10 { return NX_HLL_HEULE_THRESH_LGK10 } 229 return 0 230} 231 232// log2(x) returned in PPM (parts per million), with fractional precision. 233// 234// Prior code computed integer m/zeros then floor-log2, which truncated 235// the fractional log info (e.g., log2(128/59) actually = 1.117 but 236// integer-divide gave 128/59=2 then floor-log2(2)=1 -- losing 0.117). 237// 238// This implementation keeps the fractional mantissa. For x = 2^k * (1 + frac): 239// log2(x) ≈ k + frac (linear mantissa interpolation) 240// Max error in log2 ~ 0.04 around mid-mantissa. This translates to 241// ~3% in the LC estimate -- much better than the prior ~12% from 242// dropping fractional bits entirely. 243// 244// genealogy_id: ours (linear approximation is our pragmatic choice; 245// DS uses double-precision native log2) 246// lineage_id: log_function 247func nx_hll_log2_ppm(x: i64) -> i64 { 248 if x <= 0 { return 0 } 249 if x == 1 { return 0 } 250 var k: i64 = 0 251 var t: i64 = x 252 while t > 1 { t = t >> 1; k = k + 1 } 253 let two_k: i64 = 1 << k 254 let frac_ppm: i64 = ((x - two_k) * NX_HLL_PPM_SCALE) / two_k 255 return k * NX_HLL_PPM_SCALE + frac_ppm 256} 257 258// Heule 2013 bias-correction lookup against the EMPIRICAL table 259// (hll_bias_table.nx, calibrated for OUR hash family — 2x murmur3_32 — 260// rather than the DS canonical table which was calibrated for xxhash64). 261// Table format: interleaved (raw_est_sample, corrected_n) pairs per lg_k. 262// 263// Why empirical, not DS canonical: DS's CompositeInterpolationXTable 264// expects DS's hash bias distribution. Plugging our hash family into 265// that table caused 10x worse error at small N during the 2026-05-10 266// grid-test session. Empirical regen with our actual HLL pipeline gives 267// table values matched to our hash characteristics. 268// 269// Cubic Lagrange interpolation uses nx_i128 (N2 numeric tier) for the 270// intermediate (num << 24) / den ratio to avoid i64 overflow at lg_k=10. 271// genealogy_id: heule_2013 + ours (empirical regen) + knuth_taocp_vol2 (long div for i128) 272// lineage_id: heule_bias_table 273 274func nx_hll_bias_table_get(lg_k: i64, i: i64) -> i64 { 275 if lg_k == 4 { return nx_hll_bias_lgk4(i) } 276 if lg_k == 5 { return nx_hll_bias_lgk5(i) } 277 if lg_k == 6 { return nx_hll_bias_lgk6(i) } 278 if lg_k == 7 { return nx_hll_bias_lgk7(i) } 279 if lg_k == 8 { return nx_hll_bias_lgk8(i) } 280 if lg_k == 9 { return nx_hll_bias_lgk9(i) } 281 if lg_k == 10 { return nx_hll_bias_lgk10(i) } 282 return -1 283} 284 285func nx_hll_bias_table_n(lg_k: i64) -> i64 { 286 if lg_k == 4 { return NX_HLL_BIAS_LGK4_N } 287 if lg_k == 5 { return NX_HLL_BIAS_LGK5_N } 288 if lg_k == 6 { return NX_HLL_BIAS_LGK6_N } 289 if lg_k == 7 { return NX_HLL_BIAS_LGK7_N } 290 if lg_k == 8 { return NX_HLL_BIAS_LGK8_N } 291 if lg_k == 9 { return NX_HLL_BIAS_LGK9_N } 292 if lg_k == 10 { return NX_HLL_BIAS_LGK10_N } 293 return 0 294} 295 296// Cubic Lagrange interpolation against the empirical table. 297// Uses nx_i128 (N2 numeric tier) for the (num << 24) / den intermediate 298// to avoid i64 overflow at the larger lg_k values: num can reach 299// ~1e9 in cardinality units; num << 24 = ~1.7e16 fits comfortably here 300// but i128 keeps us safe under expanded ranges. 301// 302// genealogy_id: heule_2013 + ours (empirical regen); 303// knuth_taocp_vol2 (long division) for the i128 backend 304// lineage_id: heule_bias_table 305 306const NX_HLL_LAGRANGE_Q: i64 = 24 // 24-bit fractional Q-format 307const NX_HLL_LAGRANGE_Q_SCALE: i64 = 16777216 // 1 << 24 308 309func nx_hll_bias_correct(lg_k: i64, raw_est: i64) -> i64 { 310 let n_samples: i64 = nx_hll_bias_table_n(lg_k) 311 if n_samples <= 0 { return raw_est } 312 313 // Bracket search. Table is interleaved (X, Y, X, Y, ...) -- X at 314 // even indices, Y at odd. n_samples is the count of (X, Y) pairs. 315 var i: i64 = 0 316 var found: i64 = -1 317 while i < n_samples - 1 { 318 let x_lo: i64 = nx_hll_bias_table_get(lg_k, i * 2) 319 let x_hi: i64 = nx_hll_bias_table_get(lg_k, (i + 1) * 2) 320 if x_lo <= raw_est { 321 if raw_est <= x_hi { found = i } 322 } 323 i = i + 1 324 } 325 if found < 0 { return raw_est } 326 327 // Pick 4 surrounding points; clamp to table edges. 328 var i0: i64 = found - 1 329 var i1: i64 = found 330 var i2: i64 = found + 1 331 var i3: i64 = found + 2 332 if i0 < 0 { 333 i0 = 0 334 i1 = 1 335 i2 = 2 336 i3 = 3 337 } 338 if i3 >= n_samples { 339 i3 = n_samples - 1 340 i2 = n_samples - 2 341 i1 = n_samples - 3 342 i0 = n_samples - 4 343 } 344 let x0: i64 = nx_hll_bias_table_get(lg_k, i0 * 2) 345 let y0: i64 = nx_hll_bias_table_get(lg_k, i0 * 2 + 1) 346 let x1: i64 = nx_hll_bias_table_get(lg_k, i1 * 2) 347 let y1: i64 = nx_hll_bias_table_get(lg_k, i1 * 2 + 1) 348 let x2: i64 = nx_hll_bias_table_get(lg_k, i2 * 2) 349 let y2: i64 = nx_hll_bias_table_get(lg_k, i2 * 2 + 1) 350 let x3: i64 = nx_hll_bias_table_get(lg_k, i3 * 2) 351 let y3: i64 = nx_hll_bias_table_get(lg_k, i3 * 2 + 1) 352 let dx0: i64 = raw_est - x0 353 let dx1: i64 = raw_est - x1 354 let dx2: i64 = raw_est - x2 355 let dx3: i64 = raw_est - x3 356 357 // L_k(x) = product over j!=k of (x - x_j) / (x_k - x_j) 358 // For each k compute num_k = product of three (raw - x_j) (i64); 359 // den_k = product of three (x_k - x_j) (i64); then the ratio in 360 // Q24 fixed-point via i128 intermediate (handles num << 24 overflow). 361 let num0: i64 = dx1 * dx2 * dx3 362 let den0: i64 = (x0 - x1) * (x0 - x2) * (x0 - x3) 363 let num1: i64 = dx0 * dx2 * dx3 364 let den1: i64 = (x1 - x0) * (x1 - x2) * (x1 - x3) 365 let num2: i64 = dx0 * dx1 * dx3 366 let den2: i64 = (x2 - x0) * (x2 - x1) * (x2 - x3) 367 let num3: i64 = dx0 * dx1 * dx2 368 let den3: i64 = (x3 - x0) * (x3 - x1) * (x3 - x2) 369 if den0 == 0 { return raw_est } 370 if den1 == 0 { return raw_est } 371 if den2 == 0 { return raw_est } 372 if den3 == 0 { return raw_est } 373 374 // coef_q24 = (num << 24) / den via i128 intermediate. 375 let c0_q24: i64 = nx_mulshl_div_i64(num0, 1, NX_HLL_LAGRANGE_Q, den0) 376 let c1_q24: i64 = nx_mulshl_div_i64(num1, 1, NX_HLL_LAGRANGE_Q, den1) 377 let c2_q24: i64 = nx_mulshl_div_i64(num2, 1, NX_HLL_LAGRANGE_Q, den2) 378 let c3_q24: i64 = nx_mulshl_div_i64(num3, 1, NX_HLL_LAGRANGE_Q, den3) 379 380 // term = y * coef_q24, descale by >> 24. Sum then round. 381 let sum_q24: i64 = y0 * c0_q24 + y1 * c1_q24 + y2 * c2_q24 + y3 * c3_q24 382 return sum_q24 / NX_HLL_LAGRANGE_Q_SCALE 383} 384 385// Returns (estimate, zeros_count). Caller wraps in Approximate<i64> 386// via nx_hll_query for the typed-envelope path. 387func nx_hll_estimate(h: *Hll) -> i64 { 388 let m: i64 = h.m 389 var sum_q32: i64 = 0 390 var zeros: i64 = 0 391 var i: i64 = 0 392 while i < m { 393 let r: i64 = h.regs[i] 394 if r == 0 { zeros = zeros + 1 } 395 sum_q32 = sum_q32 + nx_hll_pow2_neg_q32(r) 396 i = i + 1 397 } 398 if sum_q32 == 0 { return m } // every register saturated; degenerate 399 let alpha_m_sq_q64: i64 = nx_hll_alpha_m_sq_q64(h.lg_k) 400 if alpha_m_sq_q64 == 0 { 401 // lg_k outside hardcoded range -- fall back to crude estimate 402 return zeros 403 } 404 let raw_est: i64 = alpha_m_sq_q64 / sum_q32 405 406 // DS composite estimator (Heule 2013 + DataSketches refinement): 407 // 1. Below table range -> Linear Counting (LC) is truth 408 // 2. Above table range -> raw HLL (asymptotic bias ~ 0) 409 // 3. In-range, corrected > peg -> bias-corrected (mid+large) 410 // 4. In-range, corrected <= peg -> min(bias-corrected, LC) (small overlap) 411 // 412 // The LC peg = LC_PEG_NUM / LC_PEG_DEN * K smooths the LC/bias-corrected 413 // transition. Source: DataSketches HllUtil.HLL_NON_HIP_RSE_FACTOR 414 // (0.7 constant); rationale per Heule 2013 §4. 415 // 416 // genealogy_id: heule_2013 + datasketches (composite estimator); 417 // lineage_ids: lc_fallback (low), heule_bias_table (mid), 418 // alpha_m_correction (high) 419 let n_samples: i64 = nx_hll_bias_table_n(h.lg_k) 420 let first_x: i64 = nx_hll_bias_table_get(h.lg_k, 0) 421 let last_x: i64 = nx_hll_bias_table_get(h.lg_k, (n_samples - 1) * 2) 422 let K: i64 = 1 << h.lg_k 423 let lc_peg: i64 = (K * NX_HLL_LC_PEG_NUM) / NX_HLL_LC_PEG_DEN 424 425 // LC estimate (cheap; we already have zeros count). 426 var lc_est: i64 = -1 427 if zeros > 0 { 428 let log2_m_ppm: i64 = h.lg_k * NX_HLL_PPM_SCALE 429 let log2_z_ppm: i64 = nx_hll_log2_ppm(zeros) 430 let log2_diff_ppm: i64 = log2_m_ppm - log2_z_ppm 431 let ln_diff_ppm: i64 = (log2_diff_ppm * NX_HLL_LN2_PPM) / NX_HLL_PPM_SCALE 432 lc_est = (m * ln_diff_ppm) / NX_HLL_PPM_SCALE 433 } 434 435 if raw_est < first_x { 436 if lc_est >= 0 { return lc_est } 437 return raw_est 438 } 439 if raw_est > last_x { 440 return raw_est 441 } 442 let corrected: i64 = nx_hll_bias_correct(h.lg_k, raw_est) 443 if corrected > lc_peg { 444 return corrected 445 } 446 if lc_est >= 0 { 447 if corrected < lc_est { return corrected } 448 return lc_est 449 } 450 return corrected 451} 452 453// === typed query =================================================== 454// 455// Returns Approximate<i64> with rel_stddev envelope: 456// stddev_rel = 1.04 / sqrt(m), in parts-per-billion. 457// For lg_k=12 (m=4096), 1.04/64 = 0.01625 -> 16_250_000 ppb. 458// We hardcode per lg_k since sqrt isn't a substrate primitive yet. 459 460func nx_hll_stddev_rel_ppb(lg_k: i64) -> i64 { 461 if lg_k == 4 { return 260000000 } // 0.260 462 if lg_k == 5 { return 184000000 } // 0.184 463 if lg_k == 6 { return 130000000 } // 0.130 464 if lg_k == 7 { return 92000000 } // 0.092 465 if lg_k == 8 { return 65000000 } // 0.065 466 if lg_k == 9 { return 46000000 } // 0.046 467 if lg_k == 10 { return 32500000 } // 0.0325 468 if lg_k == 11 { return 23000000 } // 0.023 469 if lg_k == 12 { return 16250000 } // 0.01625 470 if lg_k == 13 { return 11500000 } // 0.0115 471 if lg_k == 14 { return 8125000 } // 0.008125 472 if lg_k == 15 { return 5750000 } // 0.00575 473 return 1000000000 474} 475 476func nx_hll_query(h: *Hll) -> *ApproxI64 { 477 let est: i64 = nx_hll_estimate(h) 478 let stddev_ppb: i64 = nx_hll_stddev_rel_ppb(h.lg_k) 479 return nx_approx_new(est, NX_ENV_REL_STDDEV, stddev_ppb, 480 682700000, // conf 0.6827 = ±1σ 481 NX_MATURITY_REFERENCE_IMPL, 482 NX_ADV_HONEST) 483} 484 485// === merge ========================================================= 486 487func nx_hll_merge(a: *Hll, b: *Hll) -> *Hll { 488 if a.lg_k != b.lg_k { return 0 as *Hll } 489 if a.seed != b.seed { return 0 as *Hll } 490 let out: *Hll = nx_hll_alloc(a.lg_k, a.seed) 491 var i: i64 = 0 492 while i < a.m { 493 let va: i64 = a.regs[i] 494 let vb: i64 = b.regs[i] 495 if va > vb { out.regs[i] = va } 496 if va <= vb { out.regs[i] = vb } 497 i = i + 1 498 } 499 return out 500}