code wiki / _hdl_build / nx_research_discover_gate.nx
nx_research_discover_gate.nx
buildroot/runtime/_hdl_build/nx_research_discover_gate.nx
about
nx_research_discover_gate.nx -- the research loop crosses from REPRODUCTION to DISCOVERY (operator:
"use the verifiers to validate NEW candidates -- low-mult schemes / search, not just reproduction").
The reproduction gates (nx_research_sim/strassen4/chem/phys) replay KNOWN published results. This gate
has the system DISCOVER a scheme it was never given, then proves it exact -- the AlphaTensor paradigm
("Discovering faster matrix multiplication" -- foundationed in our library) applied to EXPONENTIATION:
PROBLEM : the minimum number of multiplications to compute x^n is the length of the shortest
ADDITION CHAIN for n (1=a0<a1<...<aL=n, each ak = ai+aj of two earlier terms).
BASELINE : the standard binary square-and-multiply method costs (bitlen(n)-1)+(popcount(n)-1) muls.
DISCOVERY : an iterative-deepening search finds the PROVABLY-MINIMAL chain. For many n it is STRICTLY
SHORTER than binary (n=15: 5 vs 6; n=23: 6 vs 7) -- a real, measured, faster scheme found
by search, not supplied.
VERIFIER : the exact-comparison substrate a discovery loop needs -- the discovered chain is re-validated
structurally AND must compute x^n == naive repeated-multiply over a (base, prime) grid
(modular exponentiation, exact). A BROKEN chain is REJECTED (liar-kill), and where binary is
already optimal (n=16) the harness reports improvement=0 -- it never fabricates a discovery.
Pure integer algebra, no float, deterministic, reproducible by anyone. GREEN iff 8/8. license_tier: ORIGINAL
dependencies 2 imports · 0 importers
imports: nx_syscalls.nxnx_library.nx
imported by: nobody (leaf or entry point)
call flow from main pre-order; caps 40 nodes / depth 6 declared; ↻ = already shown
structs
| none |
consts
| none |
functions
| 21 | func 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 } |
| 22 | func 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 } |
| 23 | func 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 } |
| 26 | func rs_has(buf: *u8, n: i64, needle: *u8) -> i64 called by 1: rs_lib_contains |
| 33 | func rs_lib_contains(needle: *u8) -> i64 |
| 46 | func bitlen(n: i64) -> i64 { var b: i64=0; var m: i64=n; while m>0 { b=b+1; m=m>>1 } return b } called by 1: lbin |
| 47 | func popcount(n: i64) -> i64 { var c: i64=0; var m: i64=n; while m>0 { c=c+(m&1); m=m>>1 } return c } called by 1: lbin |
| 48 | func lbin(n: i64) -> i64 { return (bitlen(n)-1) + (popcount(n)-1) } |
| 52 | func ipow2_ge(base: i64, steps: i64, n: i64) -> i64 called by 1: ac_dfs |
| 59 | func ac_dfs(a: *i64, pos: i64, L: i64, n: i64) -> i64 |
| 79 | func ac_minlen(n: i64, a: *i64, maxL: i64) -> i64 |
| 90 | func ac_step_ok(a: *i64, k: i64) -> i64 called by 1: ac_valid |
| 99 | func ac_valid(a: *i64, L: i64, n: i64) -> i64 |
| 108 | func mulmod(x: i64, y: i64, p: i64) -> i64 { return (x % p) * (y % p) % p } |
| 109 | func 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 } |
| 111 | func powmod_chain(a: *i64, L: i64, x: i64, p: i64, val: *i64) -> i64 |
| 126 | func ac_verify_exact(a: *i64, L: i64, n: i64) -> i64 |
| 142 | func 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 } |
| 144 | func main() -> i64 |