nx_intlog.nx source
↩ module page · 92 lines · 5374 B
1// nx_intlog.nx -- INTEGER fixed-point base-2 logarithm (no floats anywhere -- the ecosystem's no-float
2// doctrine). ilog2_1024(x) returns round(1024 * log2(x)) for x >= 1 via msb + 10 mantissa-squaring
3// refinement steps (each step decides one fractional bit; y stays < 2^17 so y*y < 2^34 -- no overflow).
4// The BM25/IDF ranking rung composes this: idf_q10(N, n_t) = ilog2_1024(N+1) - ilog2_1024(n_t) >= 0-ish,
5// clamped at 0 (a term in every doc carries ~no signal -- correct BM25 behavior). license_tier: ORIGINAL
6import "nx_syscalls.nx"
7
8func ilog2_1024(x0: i64) -> i64 {
9 if x0 <= 1 { return 0 }
10 var x: i64 = x0
11 // msb position
12 var msb: i64 = 0
13 var t: i64 = x
14 while t > 1 { t = t / 2; msb = msb + 1 }
15 var result: i64 = msb * 1024
16 // normalize the mantissa to Q16 in [65536, 131072): y = x * 2^16 / 2^msb (shift-split so a large
17 // x (up to 2^47) never overflows the intermediate)
18 var y: i64 = 0
19 if msb <= 16 { y = x * (65536 / (1 << msb)) } else { y = x / (1 << (msb - 16)) }
20 if y < 65536 { y = 65536 }
21 // 10 fractional bits: square the mantissa; >= 2.0 means this bit is set
22 var bit: i64 = 512
23 var i: i64 = 0
24 while i < 10 {
25 y = (y * y) >> 16
26 if y >= 131072 { y = y >> 1; result = result + bit }
27 bit = bit / 2
28 i = i + 1
29 }
30 return result
31}
32// idf in Q10: 1024*log2((N+1)/n_t), floored at 0 (never negative -- an everywhere-term scores zero)
33func idf_q10(bign: i64, nt: i64) -> i64 {
34 var n2: i64 = nt
35 if n2 < 1 { n2 = 1 }
36 let v: i64 = ilog2_1024(bign + 1) - ilog2_1024(n2)
37 if v < 0 { return 0 }
38 return v
39}
40// Robertson tf-saturation in Q10 with k1=1.2 (Q10 k1=1228): (k1+1)*tf / (tf + k1) -> (0, 2252]
41func tfsat_q10(tf: i64) -> i64 {
42 if tf <= 0 { return 0 }
43 return (tf * 1024 * 2252) / (tf * 1024 + 1228)
44}
45// FULL BM25 tf-part with length normalization, Q10: (k1+1)*tf / (tf + k1*(1-b+b*|d|/avgdl)), b=0.75.
46// normq10 = 1024*|d|/avgdl (the doc's relative length; 1024 = average). normq10==1024 reduces EXACTLY to
47// tfsat_q10 (the b=0 ladder rung stays a special case, gate-pinned). Longer-than-average docs score lower,
48// shorter higher -- the classic BM25 verbosity correction, still integer-only.
49func tfnorm_q10(tf: i64, normq10: i64) -> i64 {
50 if tf <= 0 { return 0 }
51 var nq: i64 = normq10
52 if nq < 64 { nq = 64 } // floor 1/16 avg (a 3-word doc must not explode the score)
53 if nq > 16384 { nq = 16384 } // cap 16x avg
54 let lenfac: i64 = 256 + ((768 * nq) >> 10) // Q10: (1-b) + b*rel-length, b=0.75
55 return (tf * 1024 * 2252) / (tf * 1024 + ((1228 * lenfac) >> 10))
56}
57// BM25Q QUERY-SIDE SATURATION (search rung S5, 2026-09-15; bm25q26 = Sharifymoghaddam, Ge, Lin, SIGIR 2026 repro track):
58// a query term that repeats is worth MORE than one seen once, but not qtf times more -- the same Robertson saturation
59// the document side has always had, applied to the query-term frequency. qtfsat_q10(1) is EXACTLY 1024 in this integer
60// form ((1024*2252)/(1024+1228) has no remainder), so a term seen once weighs exactly what plain BM25 gives it: the
61// anti-vacuity property the rung pre-declared (a single-term query scores identically under both) holds by construction,
62// not by tolerance. The query-side k is its own named constant (rule 11) and starts equal to k1.
63// RRF (Cormack, Clarke and Buettcher 2009) reciprocal-rank fusion constant, ONE spelling for the estate (2026-09-16):
64// the harness fusion arms (nx_beir_eval R1b and S5) and the served scorer (nx_docportal_search_seg dss_bm25q_fuse)
65// must fuse with the same k, or a served ranking is not the ranking the leaderboard row measured. 60 is the paper's
66// value and the value every arm on the search board was measured at.
67const RRF_K_STD: i64 = 60
68const BM25Q_K_Q10: i64 = 1228
69func qtfsat_q10(qtf: i64) -> i64 {
70 if qtf <= 0 { return 0 }
71 return (qtf * 1024 * (1024 + BM25Q_K_Q10)) / (qtf * 1024 + BM25Q_K_Q10)
72}
73// the BM25Q weight of a term given ANY Q10 idf (the caller keeps its own idf convention) and its query-term frequency:
74// the idf scaled by the saturated qtf. qtf=1 returns the idf UNCHANGED, exactly.
75func idf_bm25q(idf: i64, qtf: i64) -> i64 {
76 if qtf <= 0 { return 0 }
77 return (idf * qtfsat_q10(qtf)) >> 10
78}
79// CORPUS-SCALE SIDE OF THE PUBLISHED BM25 CROSSOVER (search rung S1, 2026-09-14). The scaling study cited on
80// /compare/search as bm25scale26 found BM25 overtaking agentic retrieval around 10 million corpus tokens and
81// leading at every larger shared tier. The crossover itself is DATA (knowledge/search_crossover.conf), never
82// a literal here: this decides only which side a measured corpus sits on, and at the crossover it is ABOVE
83// because the study reports BM25 leading FROM that tier on. Pure, so nx_intlog_gate drives it in-process.
84const CS_SIDE_BELOW: i64 = 0
85const CS_SIDE_ABOVE: i64 = 1
86const CS_SIDE_UNMEASURED: i64 = 0 - 1 // THREE STATES, NOT TWO (the contract nx_qrels_bench carried first, 2026-09-04): an unmeasured corpus or threshold can never read BELOW -- abstain, never acquit
87func cs_crossover(corpus_tokens: i64, crossover_tokens: i64) -> i64 {
88 if crossover_tokens <= 0 { return CS_SIDE_UNMEASURED }
89 if corpus_tokens <= 0 { return CS_SIDE_UNMEASURED }
90 if corpus_tokens >= crossover_tokens { return CS_SIDE_ABOVE }
91 return CS_SIDE_BELOW
92}