nx_research_discover_gate.nx source

1// nx_research_discover_gate.nx -- the research loop crosses from REPRODUCTION to DISCOVERY (operator: 2// "use the verifiers to validate NEW candidates -- low-mult schemes / search, not just reproduction"). 3// 4// The reproduction gates (nx_research_sim/strassen4/chem/phys) replay KNOWN published results. This gate 5// has the system DISCOVER a scheme it was never given, then proves it exact -- the AlphaTensor paradigm 6// ("Discovering faster matrix multiplication" -- foundationed in our library) applied to EXPONENTIATION: 7// PROBLEM : the minimum number of multiplications to compute x^n is the length of the shortest 8// ADDITION CHAIN for n (1=a0<a1<...<aL=n, each ak = ai+aj of two earlier terms). 9// BASELINE : the standard binary square-and-multiply method costs (bitlen(n)-1)+(popcount(n)-1) muls. 10// DISCOVERY : an iterative-deepening search finds the PROVABLY-MINIMAL chain. For many n it is STRICTLY 11// SHORTER than binary (n=15: 5 vs 6; n=23: 6 vs 7) -- a real, measured, faster scheme found 12// by search, not supplied. 13// VERIFIER : the exact-comparison substrate a discovery loop needs -- the discovered chain is re-validated 14// structurally AND must compute x^n == naive repeated-multiply over a (base, prime) grid 15// (modular exponentiation, exact). A BROKEN chain is REJECTED (liar-kill), and where binary is 16// already optimal (n=16) the harness reports improvement=0 -- it never fabricates a discovery. 17// Pure integer algebra, no float, deterministic, reproducible by anyone. GREEN iff 8/8. license_tier: ORIGINAL 18import "nx_syscalls.nx" 19import "nx_library.nx" 20 21func g_w(s: *u8) -> i64 { var n: i64=0; while s[n]!=(0 as u8){n=n+1} sys_write(1,s,n); return 0 } 22func g_n(v: i64) -> i64 { var m: i64=v; if m<0{g_w("-");m=0-m} let t:*u8=sys_mmap(24); var k:i64=0; if m==0{t[0]=48 as u8;k=1}; while m>0{t[k]=(48+(m%10)) as u8;m=m/10;k=k+1}; var i:i64=0; let o:*u8=sys_mmap(24); while i<k{o[i]=t[k-1-i];i=i+1}; sys_write(1,o,k); return 0 } 23func g_row(id: *u8, ok: i64, pass: *i64) -> i64 { g_w(" "); g_w(id); g_w(": "); if ok==1 { g_w("OK\n"); pass[0]=pass[0]+1 } else { g_w("FAIL\n") } return 0 } 24 25// ---- RESEARCHER: locate the discovery-of-faster-computation research in our no-link-rot library ---- 26func rs_has(buf: *u8, n: i64, needle: *u8) -> i64 { 27 var nl: i64=0; while needle[nl]!=(0 as u8){nl=nl+1} 28 if nl==0 { return 0 } 29 var i: i64=0 30 while i+nl<=n { var j: i64=0; var ok: i64=1; while j<nl { if buf[i+j]!=needle[j]{ok=0;j=nl}else{j=j+1} } if ok==1 {return 1} i=i+1 } 31 return 0 32} 33func rs_lib_contains(needle: *u8) -> i64 { 34 let cids: *i64 = sys_mmap(8*256) as *i64 35 let cnt: i64 = lib_list(cids, 256) 36 let pp: *i64 = sys_mmap(8) as *i64; let ll: *i64 = sys_mmap(8) as *i64 37 var d: i64 = 0 38 while d < cnt { 39 if lib_get(cids[d] as *u8, pp, ll) == 1 { if rs_has(pp[0] as *u8, ll[0], needle) == 1 { return 1 } } 40 d = d + 1 41 } 42 return 0 43} 44 45// ---- BASELINE: cost of the standard binary square-and-multiply method ---- 46func bitlen(n: i64) -> i64 { var b: i64=0; var m: i64=n; while m>0 { b=b+1; m=m>>1 } return b } 47func popcount(n: i64) -> i64 { var c: i64=0; var m: i64=n; while m>0 { c=c+(m&1); m=m>>1 } return c } 48func lbin(n: i64) -> i64 { return (bitlen(n)-1) + (popcount(n)-1) } 49 50// ---- DISCOVERY: iterative-deepening DFS for the provably-minimal addition chain ---- 51// can `base` reach n within `steps` doublings (each step at most doubles)? -> magnitude prune. 52func ipow2_ge(base: i64, steps: i64, n: i64) -> i64 { 53 var reach: i64 = base; var s: i64 = 0 54 while s < steps { reach = reach + reach; s = s + 1; if reach >= n { return 1 } } 55 if reach >= n { return 1 } 56 return 0 57} 58// a[0..pos-1] filled (ascending, a[0]=1); try to fill pos..L so a[L]==n. ascending chains suffice for minimal length. 59func ac_dfs(a: *i64, pos: i64, L: i64, n: i64) -> i64 { 60 if pos == L+1 { if a[L]==n { return 1 } return 0 } 61 let last: i64 = a[pos-1] 62 if ipow2_ge(last, L-pos+1, n) == 0 { return 0 } 63 var i: i64 = pos-1 64 while i >= 0 { 65 var j: i64 = i 66 while j >= 0 { 67 let cand: i64 = a[i] + a[j] 68 if cand > last { if cand <= n { 69 a[pos] = cand 70 if ac_dfs(a, pos+1, L, n) == 1 { return 1 } 71 } } 72 j = j - 1 73 } 74 i = i - 1 75 } 76 return 0 77} 78// minimal chain length for n (fills a[0..L]); -1 if none <= maxL. first depth that succeeds == provable minimum. 79func ac_minlen(n: i64, a: *i64, maxL: i64) -> i64 { 80 var L: i64 = 1 81 while L <= maxL { 82 a[0] = 1 83 if ac_dfs(a, 1, L, n) == 1 { return L } 84 L = L + 1 85 } 86 return -1 87} 88 89// ---- VERIFIER: independent structural validation (does not trust the search) ---- 90func ac_step_ok(a: *i64, k: i64) -> i64 { 91 var i: i64 = 0 92 while i < k { 93 var j: i64 = 0 94 while j < k { if a[i]+a[j]==a[k] { return 1 } j = j + 1 } 95 i = i + 1 96 } 97 return 0 98} 99func ac_valid(a: *i64, L: i64, n: i64) -> i64 { 100 if a[0] != 1 { return 0 } 101 var k: i64 = 1 102 while k <= L { if ac_step_ok(a, k)==0 { return 0 } k = k + 1 } 103 if a[L] != n { return 0 } 104 return 1 105} 106 107// ---- VERIFIER: functional exactness via modular exponentiation ---- 108func mulmod(x: i64, y: i64, p: i64) -> i64 { return (x % p) * (y % p) % p } 109func powmod_naive(x: i64, n: i64, p: i64) -> i64 { var r: i64 = 1 % p; var c: i64 = 0; while c < n { r = mulmod(r, x, p); c = c + 1 } return r } 110// evaluate x^n mod p along the chain: val[k]=x^(a[k]) mod p = val[i]*val[j] for any decomposition a[k]=a[i]+a[j]. 111func powmod_chain(a: *i64, L: i64, x: i64, p: i64, val: *i64) -> i64 { 112 val[0] = x % p 113 var k: i64 = 1 114 while k <= L { 115 var i: i64 = 0 116 while i < k { 117 var j: i64 = 0 118 while j < k { if a[i]+a[j]==a[k] { val[k] = mulmod(val[i], val[j], p) } j = j + 1 } 119 i = i + 1 120 } 121 k = k + 1 122 } 123 return val[L] 124} 125// the discovered chain must compute x^n == naive over a (base, prime) grid -- exact comparison. 126func ac_verify_exact(a: *i64, L: i64, n: i64) -> i64 { 127 let val: *i64 = sys_mmap(8*64) as *i64 128 let ps: *i64 = sys_mmap(64) as *i64; ps[0]=1000003; ps[1]=998244353; ps[2]=1000000007 129 let xs: *i64 = sys_mmap(64) as *i64; xs[0]=2; xs[1]=3; xs[2]=5; xs[3]=7 130 var pi: i64=0 131 while pi<3 { 132 var xi: i64=0 133 while xi<4 { 134 if powmod_chain(a, L, xs[xi], ps[pi], val) != powmod_naive(xs[xi], n, ps[pi]) { return 0 } 135 xi = xi + 1 136 } 137 pi = pi + 1 138 } 139 return 1 140} 141 142func ac_print(a: *i64, L: i64) -> i64 { var k: i64=0; while k<=L { if k>0 { g_w(",") } g_n(a[k]); k=k+1 } return 0 } 143 144func main() -> i64 { 145 let pass: *i64 = sys_mmap(8) as *i64; pass[0]=0 146 g_w("=== NX-RESEARCH-DISCOVER GATE (DISCOVERY: search finds minimal-multiplication x^n schemes, verified exact) ===\n") 147 148 let found: i64 = rs_lib_contains("matrix multiplication" as *u8) 149 150 let lb15: i64 = lbin(15); let lb23: i64 = lbin(23); let lb16: i64 = lbin(16) 151 152 let a15: *i64 = sys_mmap(8*64) as *i64 153 let a23: *i64 = sys_mmap(8*64) as *i64 154 let a16: *i64 = sys_mmap(8*64) as *i64 155 let l15: i64 = ac_minlen(15, a15, 20) 156 let l23: i64 = ac_minlen(23, a23, 20) 157 let l16: i64 = ac_minlen(16, a16, 20) 158 159 // MINIMALITY: prove no chain one shorter than the discovery reaches 15 160 let sc: *i64 = sys_mmap(8*64) as *i64; sc[0]=1 161 let no_shorter15: i64 = (ac_dfs(sc, 1, l15-1, 15)==0) as i64 162 163 let ver15: i64 = ac_verify_exact(a15, l15, 15) 164 let ver23: i64 = ac_verify_exact(a23, l23, 23) 165 166 let val15ok: i64 = ac_valid(a15, l15, 15) 167 let val23ok: i64 = ac_valid(a23, l23, 23) 168 169 // LIAR-KILL: broken candidate chains for n=15 170 let b1: *i64 = sys_mmap(8*64) as *i64; b1[0]=1; b1[1]=2; b1[2]=3; b1[3]=7; b1[4]=12; b1[5]=15 // 7 != sum of two priors 171 let b2: *i64 = sys_mmap(8*64) as *i64; b2[0]=1; b2[1]=2; b2[2]=3; b2[3]=6; b2[4]=12; b2[5]=14 // valid steps, wrong endpoint 172 let rej1: i64 = (ac_valid(b1, 5, 15)==0) as i64 173 let rej2: i64 = (ac_valid(b2, 5, 15)==0) as i64 174 175 g_w(" researcher: discovery-of-faster-computation research in library = "); g_n(found); g_w("\n") 176 g_w(" n=15: binary(square&multiply)="); g_n(lb15); g_w(" muls discovered minimal="); g_n(l15); g_w(" chain=["); ac_print(a15,l15); g_w("]\n") 177 g_w(" n=23: binary="); g_n(lb23); g_w(" muls discovered minimal="); g_n(l23); g_w(" chain=["); ac_print(a23,l23); g_w("]\n") 178 g_w(" n=16: binary="); g_n(lb16); g_w(" muls discovered minimal="); g_n(l16); g_w(" improvement="); g_n(lb16-l16); g_w("\n") 179 g_w(" verify-exact (x^n chain==naive over (base,prime) grid): x^15="); g_n(ver15); g_w(" x^23="); g_n(ver23); g_w("\n") 180 g_w(" liar-kill: broken(invalid-step) rejected="); g_n(rej1); g_w(" broken(wrong-endpoint) rejected="); g_n(rej2); g_w("\n") 181 182 g_row("RESEARCHER: discovery-of-faster-computation research (AlphaTensor) foundationed in library" as *u8, found, pass) 183 184 var base_ok: i64 = 0 185 if lb15==6 { if lb16==4 { if lb23==7 { base_ok=1 } } } 186 g_row("BASELINE: binary square&multiply costs correct (15->6, 16->4, 23->7 muls)" as *u8, base_ok, pass) 187 188 var disc15: i64 = 0 189 if l15==5 { if l15<lb15 { if val15ok==1 { disc15=1 } } } 190 g_row("DISCOVERY n=15: search finds a STRICTLY SHORTER valid scheme than binary (5<6)" as *u8, disc15, pass) 191 192 g_row("MINIMALITY n=15: exhaustive search finds NO length-4 chain (discovered 5 is minimal)" as *u8, no_shorter15, pass) 193 194 g_row("VERIFY-EXACT n=15: discovered chain computes x^15 == naive repeated-multiply (mod-p grid)" as *u8, ver15, pass) 195 196 var disc23: i64 = 0 197 if l23==6 { if l23<lb23 { if ver23==1 { if val23ok==1 { disc23=1 } } } } 198 g_row("SECOND DISCOVERY n=23: search finds 6<7, verified exact (not a one-off)" as *u8, disc23, pass) 199 200 var honest: i64 = 0 201 if l16==4 { if l16==lb16 { honest=1 } } 202 g_row("HONEST NO-OVERCLAIM n=16: binary already optimal -> improvement=0, no fabricated discovery" as *u8, honest, pass) 203 204 var liar: i64 = 0 205 if rej1==1 { if rej2==1 { liar=1 } } 206 g_row("LIAR-KILL: broken chains (invalid step / wrong endpoint) REJECTED by the validator" as *u8, liar, pass) 207 208 g_w("RESEARCH-DISCOVER-GATE rows=8 pass="); g_n(pass[0]) 209 if pass[0]==8 { g_w(" verdict=GREEN\n"); sys_exit(0); return 0 } 210 g_w(" verdict=RED\n"); sys_exit(1); return 1 211}