nx_mulchain_deep.nx source

1// nx_mulchain_deep.nx -- the DEEPENED chain search (the team's answer to its own escalation: 2// "constants exceed imul cost -- author imul or deepen the search?"). 3// 4// THEORY (researched, not hand-waved): finding the shortest op-chain for c*x is computing a 5// length-/time-BOUNDED KOLMOGOROV COMPLEXITY of that function over our instruction set. The 6// unbounded version is uncomputable (Berry/halting); we only escape that because our ops are 7// loop-free + total + length-capped. The principled search order is LEVIN's universal search: 8// shortest-first, bounding by length AND cost (Kt = |program| + log time). Our iterative 9// deepening over op-count IS Levin shortest-first; the `+log time` term is the cost cap below. 10// Two prunes keep it tractable: 11// (1) REACHABILITY (the THURBER bound, generalized): an addition-chain element at most 12// DOUBLES per step (prune when 2^m * a_i < n); our op set grows faster (SHL by maxsh, 13// LEA +3 bits), so we use maxmag << (G*rem) < |C| with G = max(maxsh,4). COMPLETE 14// (never prunes a reachable target), collapses the dead subtrees that hung the prime case. 15// (2) COST CAP (Levin's +log time): a serial chain of N 1-cycle ops ~ N cycles latency vs 16// imul ~3 cycles, so searching past the cost-competitive depth is pointless -> cap maxL. 17// NB: the classic Hamming-weight lower bounds (Schonhage log2 n + log2 v(n)) DON'T transfer 18// here -- SHL/LEA do many doublings in one op, so our minimal chains are shorter and those 19// bounds under-count us. The reach bound + cost cap are what actually apply to our op set. 20// Refs: Kolmogorov complexity (uncomputable); Levin universal search / Kt; Thurber 1999 21// (addition-chain branch-and-bound). license_tier: ORIGINAL 22 23import "nx_mulchain.nx" // SO_* ops, mc_abs, mc_avslot, mc_eval, mulchain_find (shallow) 24import "nx_search_governor.nx" // the shared cost-bounded-search judgment (sg_decide, sg_cost_cap) 25 26// max |value| over the operands available at step t: slot 0 (=x) and computed slots 3..t+2. 27func mcd_maxmag(sv: *i64, t: i64) -> i64 { 28 var mx: i64 = mc_abs(sv[0]); var s: i64 = 3 29 while s <= t + 2 { let v: i64 = mc_abs(sv[s]); if v > mx { mx = v } s = s + 1 } 30 return mx 31} 32 33// REACHABILITY: can |C| still be produced in `rem` ops, starting from max magnitude M, given 34// per-op bit-growth G? Upper bound on reachable magnitude = M << (G*rem). Guarded vs overflow. 35func mcd_reach(M: i64, rem: i64, G: i64, C: i64) -> i64 { 36 if rem <= 0 { return 1 } 37 let sh: i64 = G * rem 38 if sh >= 62 { return 1 } // bound exceeds i64 range -> assume reachable 39 if (M << sh) >= mc_abs(C) { return 1 } 40 return 0 41} 42 43// pruned iterative-deepening enumeration (mirrors mc_enum but with the reach prune up front). 44func mcd_enum(op: *i64, a: *i64, b: *i64, t: i64, L: i64, sv: *i64, C: i64, bound: i64, maxsh: i64, G: i64) -> i64 { 45 if t == L { if sv[L + 2] == C { return 1 } return 0 } 46 // FAIL-FAST: if even maximal growth can't reach |C| in the remaining (L-t) ops, give up here. 47 if mcd_reach(mcd_maxmag(sv, t), L - t, G, C) == 0 { return 0 } 48 let nav: i64 = t + 1 49 let rslot: i64 = t + 3 50 // ADD (i <= j) 51 var i: i64 = 0 52 while i < nav { 53 var j: i64 = i 54 while j < nav { 55 let nv: i64 = sv[mc_avslot(i)] + sv[mc_avslot(j)] 56 if mc_abs(nv) <= bound { 57 sv[rslot] = nv; op[t] = SO_ADD; a[t] = mc_avslot(i); b[t] = mc_avslot(j) 58 if mcd_enum(op, a, b, t + 1, L, sv, C, bound, maxsh, G) == 1 { return 1 } 59 } 60 j = j + 1 61 } 62 i = i + 1 63 } 64 // SUB (ordered) 65 i = 0 66 while i < nav { 67 var j: i64 = 0 68 while j < nav { 69 if i != j { 70 let nv: i64 = sv[mc_avslot(i)] - sv[mc_avslot(j)] 71 if mc_abs(nv) <= bound { 72 sv[rslot] = nv; op[t] = SO_SUB; a[t] = mc_avslot(i); b[t] = mc_avslot(j) 73 if mcd_enum(op, a, b, t + 1, L, sv, C, bound, maxsh, G) == 1 { return 1 } 74 } 75 } 76 j = j + 1 77 } 78 i = i + 1 79 } 80 // SHL by 1..maxsh 81 i = 0 82 while i < nav { 83 var sh: i64 = 1 84 while sh <= maxsh { 85 let nv: i64 = sv[mc_avslot(i)] << sh 86 if mc_abs(nv) <= bound { 87 sv[rslot] = nv; op[t] = SO_SHL; a[t] = mc_avslot(i); b[t] = sh 88 if mcd_enum(op, a, b, t + 1, L, sv, C, bound, maxsh, G) == 1 { return 1 } 89 } 90 sh = sh + 1 91 } 92 i = i + 1 93 } 94 // LEA: base + index*{2,4,8} 95 i = 0 96 while i < nav { 97 var j2: i64 = 0 98 while j2 < nav { 99 var si: i64 = 0 100 while si < 3 { 101 var sc: i64 = 2 102 if si == 1 { sc = 4 } 103 if si == 2 { sc = 8 } 104 let nv: i64 = sv[mc_avslot(i)] + sv[mc_avslot(j2)] * sc 105 if mc_abs(nv) <= bound { 106 var oo: i64 = SO_LEA2 107 if sc == 4 { oo = SO_LEA4 } 108 if sc == 8 { oo = SO_LEA8 } 109 sv[rslot] = nv; op[t] = oo; a[t] = mc_avslot(i); b[t] = mc_avslot(j2) 110 if mcd_enum(op, a, b, t + 1, L, sv, C, bound, maxsh, G) == 1 { return 1 } 111 } 112 si = si + 1 113 } 114 j2 = j2 + 1 115 } 116 i = i + 1 117 } 118 return 0 119} 120 121// deepened find: shortest chain for x*C over lengths 1..maxL, pruned so hopeless constants 122// fail fast. maxsh caps single-shift size (G = max(maxsh,4) keeps the reach bound sound vs LEA). 123func mulchain_find_deep(C: i64, maxL: i64, op: *i64, a: *i64, b: *i64) -> i64 { 124 let sv: *i64 = sys_mmap(8 * (maxL + 8)) as *i64 125 sv[0] = 1 126 let bound: i64 = mc_abs(C) * 4 + 8 127 let maxsh: i64 = 6 128 var G: i64 = maxsh 129 if G < 4 { G = 4 } 130 var L: i64 = 1 131 while L <= maxL { 132 if mcd_enum(op, a, b, 0, L, sv, C, bound, maxsh, G) == 1 { return L } 133 L = L + 1 134 } 135 return 0 136} 137 138// VERIFIED deepened find: returns minimal op count only if the chain provably computes c*x on 139// independent inputs (the Engineer's verify-don't-trust), else -1 (cede to imul / not found). 140func mulchain_deep_verified(c: i64, maxL: i64, op: *i64, a: *i64, b: *i64) -> i64 { 141 let L: i64 = mulchain_find_deep(c, maxL, op, a, b) 142 if L <= 0 { return 0 - 1 } 143 if mc_eval(op, a, b, L, 7) != c * 7 { return 0 - 1 } 144 if mc_eval(op, a, b, L, 131) != c * 131 { return 0 - 1 } 145 if mc_eval(op, a, b, L, 0 - 9) != c * (0 - 9) { return 0 - 1 } 146 return L 147} 148 149// COST SELECTION (the escalation's real answer): the deepened search alone doesn't beat imul -- 150// a chain of N serial 1-cycle ops costs ~N cycles, imul ~3. So the team SEARCHES to `cap` and 151// picks the cost-winner. tie_thresh = the largest chain length that still beats/ties imul under 152// the chosen cost model (3 for LATENCY: chain wins at N<=2, ties at 3; larger for THROUGHPUT, 153// where cheap ops spread across ALU ports beat the single multiply unit). Data-driven (no magic 154// numbers -- the cost params are arguments). Returns the chain op-count if the chain is the 155// cost-winner, else 0 = USE IMUL. This RESOLVES "exceed imul cost?" per constant, by cost. 156const MCD_USE_IMUL: i64 = 0 // == SG_USE_BASELINE: the multiply space's baseline is imul 157func mc_cost_select(c: i64, cap: i64, tie_thresh: i64, op: *i64, a: *i64, b: *i64) -> i64 { 158 let L: i64 = mulchain_deep_verified(c, cap, op, a, b) 159 // multiply-by-constant is just ONE instance of the general principle: op_cost = 1 cycle per 160 // chain op, baseline_cost = imul's cost (tie_thresh cycles). The SAME sg_decide governs every 161 // search space -- the team applies one judgment, not a per-space rule. 162 return sg_decide(L, 1, tie_thresh) 163}