code wiki / _hdl_build / nx_evo_lcm.nx
nx_evo_lcm.nx source
↩ module page · 158 lines · 7818 B
1// nx_evo_lcm.nx -- COMPOUNDING derivation toward self-sufficiency ("adam+eve making kids,
2// their kids making kids"): derive lcm by COMPOSING the already-DERIVED gcd (a prior kid)
3// as a primitive. lcm(a,b) = a*b / gcd(a,b). The op-set gives the search the inputs a,b,
4// multiply, and a DIV-by-gcd op that calls gcd_evolved -- the structure the SEARCH derived
5// earlier (nx_evo_gcd, body [1 3 0 2]), inlined verbatim. So the derived gcd (KID) becomes
6// the building block for deriving lcm (GRANDKID) -- the lineage growing on itself, not a
7// one-off. Self-verifies the derived lcm vs true lcm across a grid. I author the MACHINE
8// (substrate); the SEARCH composes lcm; full self-sufficiency (team authors the machine +
9// an unattended loop) is the horizon this steps toward. license_tier: ORIGINAL
10import "nx_syscalls.nx"
11import "nx_itoa_lib.nx" // shared MSB-first emitter (zero-alloc)
12const LCM_MAGIC_2862933555777941757: i64 = 2862933555777941757
13const LCM_MAGIC_3037000493: i64 = 3037000493
14const LCM_MAGIC_2000000: i64 = 2000000
15const LCM_MAGIC_1000000: i64 = 1000000
16const LCM_MAGIC_2654435761: i64 = 2654435761
17const LCM_MAGIC_12345: i64 = 12345
18const LCM_MAGIC_1000000000: i64 = 1000000000
19
20const LCM_LEN: i64 = 4
21const EVO_P: i64 = 256
22const EVO_G: i64 = 2000
23const EVO_T: i64 = 5
24const NTRAIN: i64 = 6
25const NHELD: i64 = 4
26
27func lm_rand(state: *i64) -> i64 { state[0] = state[0] * LCM_MAGIC_2862933555777941757 + LCM_MAGIC_3037000493; return (state[0] >> 17) & 0x3fffffff }
28func lm_abs(x: i64) -> i64 { if x < 0 { return 0 - x } return x }
29
30// THE DERIVED gcd (a prior KID -- body [1 3 0 2] from _evo_gcd_champ.nx, search-derived).
31func gcd_evolved(a: i64, b: i64) -> i64 {
32 var r0: i64 = a; var r1: i64 = b; var swp: i64 = 0; var guard: i64 = 0
33 while r1 != 0 {
34 if guard >= 256 { r1 = 0 } else {
35 if r0 != 0 { r1 = r1 % r0 }
36 r0 = r0 - r1
37 if r1 != 0 { r0 = r0 % r1 }
38 swp = r0; r0 = r1; r1 = swp
39 guard = guard + 1
40 }
41 }
42 return r0
43}
44// true gcd/lcm oracle (independent reference).
45func lm_euclid(a: i64, b: i64) -> i64 { var x: i64 = a; var y: i64 = b; while y != 0 { let t: i64 = x % y; x = y; y = t } return x }
46func lcm_true(a: i64, b: i64) -> i64 { let g: i64 = lm_euclid(a, b); if g == 0 { return 0 } return (a * b) / g }
47
48// training/held-out (a,b) pairs (small, no overflow).
49func lm_a(i: i64) -> i64 { if i == 0 { return 6 } if i == 1 { return 4 } if i == 2 { return 3 } if i == 3 { return 8 } if i == 4 { return 9 } if i == 5 { return 10 } if i == 6 { return 7 } if i == 7 { return 12 } if i == 8 { return 5 } return 14 }
50func lm_b(i: i64) -> i64 { if i == 0 { return 4 } if i == 1 { return 6 } if i == 2 { return 5 } if i == 3 { return 12 } if i == 4 { return 6 } if i == 5 { return 15 } if i == 6 { return 3 } if i == 7 { return 8 } if i == 8 { return 10 } return 21 }
51
52// the lcm machine: acc ops over {a, b, *a, *b, /gcd_evolved}. op4 USES the derived gcd KID.
53func lcm_eval(pop: *i64, base: i64, a: i64, b: i64) -> i64 {
54 var acc: i64 = 0; var j: i64 = 0
55 while j < LCM_LEN {
56 let op: i64 = pop[base + j]
57 if op == 0 { acc = a }
58 if op == 1 { acc = b }
59 if op == 2 { acc = acc * a }
60 if op == 3 { acc = acc * b }
61 if op == 4 { let g: i64 = gcd_evolved(a, b); if g != 0 { acc = acc / g } }
62 j = j + 1
63 }
64 return acc
65}
66
67func lcm_fit(pop: *i64, base: i64) -> i64 {
68 var err: i64 = 0; var i: i64 = 0
69 while i < NTRAIN {
70 let a: i64 = lm_a(i); let b: i64 = lm_b(i)
71 let r: i64 = lcm_eval(pop, base, a, b)
72 var d: i64 = LCM_MAGIC_2000000
73 if r >= 0 { if r <= LCM_MAGIC_1000000 { d = lm_abs(r - lcm_true(a, b)) } }
74 err = err + d
75 i = i + 1
76 }
77 return err
78}
79
80func lm_randfill(pop: *i64, base: i64, state: *i64) -> i64 { var j: i64 = 0; while j < LCM_LEN { pop[base + j] = lm_rand(state) % 6; j = j + 1 } return 0 }
81func lm_tourney(fit: *i64, state: *i64) -> i64 {
82 var bi: i64 = lm_rand(state) % EVO_P; var bd: i64 = fit[bi]; var k: i64 = 1
83 while k < EVO_T { let i: i64 = lm_rand(state) % EVO_P; if fit[i] < bd { bd = fit[i]; bi = i } k = k + 1 }
84 return bi
85}
86func lm_p(s: *u8) -> i64 { var n: i64 = 0; while s[n] != (0 as u8) { n = n + 1 } sys_write(1, s, n); return 0 }
87// MIGRATED to the shared emitter (debt 1785563586). The old body mmapped a scratch buffer
88// per call and never freed it. At PAGE granularity that is 4096B leaked PER CALL -- the
89// defect that took 28.5GB of a 36GB host in nx_ts_lumadiff (2MB input, ~3.66M calls).
90// nxi_* is MSB-first, allocates NOTHING, and emits identical bytes including the sign.
91func lm_pn(v: i64) -> i64 { nxi_out(v); return 0 }
92
93func main() -> i64 {
94 let state: *i64 = sys_mmap(8) as *i64; state[0] = 7 * LCM_MAGIC_2654435761 + LCM_MAGIC_12345
95 let glen: i64 = LCM_LEN
96 let pop: *i64 = sys_mmap(EVO_P * glen * 8) as *i64
97 let nxt: *i64 = sys_mmap(EVO_P * glen * 8) as *i64
98 let fit: *i64 = sys_mmap(EVO_P * 8) as *i64
99 let best: *i64 = sys_mmap(glen * 8) as *i64
100
101 var p: i64 = 0
102 while p < EVO_P { lm_randfill(pop, p * glen, state); p = p + 1 }
103
104 var best_err: i64 = LCM_MAGIC_1000000000; var best_gen: i64 = 0 - 1; var found: i64 = 0
105 var g: i64 = 0
106 while g < EVO_G {
107 var gbest: i64 = LCM_MAGIC_1000000000; var gbp: i64 = 0
108 p = 0
109 while p < EVO_P { let e: i64 = lcm_fit(pop, p * glen); fit[p] = e; if e < gbest { gbest = e; gbp = p } p = p + 1 }
110 if gbest < best_err { best_err = gbest; var j: i64 = 0; while j < glen { best[j] = pop[gbp * glen + j]; j = j + 1 } best_gen = g }
111 if best_err == 0 { found = 1; g = EVO_G } else {
112 var j2: i64 = 0
113 while j2 < glen { nxt[j2] = best[j2]; j2 = j2 + 1 }
114 p = 1
115 while p < EVO_P {
116 let pa: i64 = lm_tourney(fit, state) * glen
117 let pb: i64 = lm_tourney(fit, state) * glen
118 let cut: i64 = (lm_rand(state) % (glen - 1)) + 1
119 var jj: i64 = 0
120 while jj < glen { if jj < cut { nxt[p*glen + jj] = pop[pa + jj] } else { nxt[p*glen + jj] = pop[pb + jj] } jj = jj + 1 }
121 let slot: i64 = lm_rand(state) % glen
122 nxt[p*glen + slot] = lm_rand(state) % 6
123 p = p + 1
124 }
125 var c: i64 = 0
126 while c < EVO_P * glen { pop[c] = nxt[c]; c = c + 1 }
127 g = g + 1
128 }
129 }
130
131 var held_ok: i64 = 0; var hi: i64 = 0
132 while hi < NHELD { let idx: i64 = NTRAIN + hi; if lcm_eval(best, 0, lm_a(idx), lm_b(idx)) == lcm_true(lm_a(idx), lm_b(idx)) { held_ok = held_ok + 1 } hi = hi + 1 }
133
134 lm_p("LCM train_err=" as *u8); lm_pn(best_err); lm_p(" gen=" as *u8); lm_pn(best_gen)
135 lm_p(" heldout=" as *u8); lm_pn(held_ok); lm_p("/" as *u8); lm_pn(NHELD)
136 if found == 1 { if held_ok == NHELD { lm_p(" GENERALIZES" as *u8) } else { lm_p(" OVERFIT" as *u8) } } else { lm_p(" NEAR" as *u8) }
137 lm_p(" ops=" as *u8)
138 var jg: i64 = 0
139 while jg < LCM_LEN { lm_pn(best[jg]); lm_p(" " as *u8); jg = jg + 1 }
140 lm_p("\n" as *u8)
141
142 // self-verify: the GRANDKID (derived lcm, built on the derived gcd KID) vs true lcm on a grid.
143 var bad: i64 = 0; var total: i64 = 0
144 var a: i64 = 1
145 while a <= 40 {
146 var b: i64 = 1
147 while b <= 40 {
148 total = total + 1
149 if lcm_eval(best, 0, a, b) != lcm_true(a, b) { bad = bad + 1 }
150 b = b + 1
151 }
152 a = a + 1
153 }
154 if bad == 0 { lm_p("LCM-COMPOUND GREEN: derived lcm (built on the derived gcd kid) == true lcm on " as *u8); lm_pn(total); lm_p(" pairs\n" as *u8) }
155 else { lm_p("LCM-COMPOUND RED mismatches=" as *u8); lm_pn(bad); lm_p("/" as *u8); lm_pn(total); lm_p("\n" as *u8) }
156 sys_exit(bad)
157 return bad
158}