nx_intlog.nx source
↩ module page · 56 lines · 2655 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}