code wiki / _hdl_build / nx_research_flip_scale_gate.nx
nx_research_flip_scale_gate.nx source
↩ module page · 180 lines · 10325 B
1// nx_research_flip_scale_gate.nx -- does the sovereign flip-graph discoverer SCALE past the 2x2 toy case?
2// Generalize the engine to arbitrary <m,n,p> matmul (multiply mxn by nxp) and DISCOVER a non-trivial rank
3// reduction in a NEW shape: <2,2,3> has naive rank 12 and proven optimum 11 (Hopcroft-Kerr). The flip/reduce
4// mechanics are dimension-agnostic (GF(2) mask XORs); only the tensor + naive builder + Brent loop need the dims.
5// Anchored on <2,2,2> (known: 8->7) to prove the generalized engine still works, then attempts <2,2,3> (12->11).
6// HONEST: 7 and 11 are the proven optima for these shapes (cited); discovered sovereignly, no AlphaTensor-record
7// claim. GREEN iff 7/7. license_tier: ORIGINAL
8import "nx_syscalls.nx"
9
10func 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 }
11func 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 }
12func 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 }
13
14func bitof(x: i64, i: i64) -> i64 { return (x>>i)&1 }
15func xrng(s: *i64) -> i64 { var x: i64=s[0]; x = x ^ (x << 13); x = x ^ (x >> 7); x = x ^ (x << 17); s[0]=x; return x }
16func rpos(s: *i64) -> i64 { let v: i64 = xrng(s); return v & 0x3FFFFFFFFFFFFFFF }
17
18// <m,n,p> matmul tensor over GF(2): a=(i1,i2)=i1*n+i2, b=(j1,j2)=j1*p+j2, c=(k1,k2)=k1*p+k2; 1 iff k1==i1,i2==j1,j2==k2.
19func build_t(t: *i64, m: i64, n: i64, p: i64) -> i64 {
20 let da: i64=m*n; let db: i64=n*p; let dc: i64=m*p
21 var a: i64=0
22 while a<da { let i1: i64=a/n; let i2: i64=a%n; var b: i64=0
23 while b<db { let j1: i64=b/p; let j2: i64=b%p; var c: i64=0
24 while c<dc { let k1: i64=c/p; let k2: i64=c%p; var val: i64=0
25 if k1==i1 { if i2==j1 { if j2==k2 { val=1 } } }
26 t[(a*db+b)*dc+c]=val; c=c+1 }
27 b=b+1 }
28 a=a+1 }
29 return 0
30}
31func build_naive(U: *i64, V: *i64, W: *i64, m: i64, n: i64, p: i64) -> i64 {
32 var idx: i64=0; var k1: i64=0
33 while k1<m { var tt: i64=0
34 while tt<n { var k2: i64=0
35 while k2<p { U[idx]=1<<(k1*n+tt); V[idx]=1<<(tt*p+k2); W[idx]=1<<(k1*p+k2); idx=idx+1; k2=k2+1 }
36 tt=tt+1 }
37 k1=k1+1 }
38 return m*n*p
39}
40func brent_gf2(U: *i64, V: *i64, W: *i64, R: i64, t: *i64, da: i64, db: i64, dc: i64) -> i64 {
41 var i: i64=0
42 while i<da { var j: i64=0
43 while j<db { var k: i64=0
44 while k<dc {
45 var acc: i64=0; var r: i64=0
46 while r<R { acc = acc ^ (bitof(U[r],i) & bitof(V[r],j) & bitof(W[r],k)); r=r+1 }
47 if acc != t[(i*db+j)*dc+k] { return 0 }
48 k=k+1 }
49 j=j+1 }
50 i=i+1 }
51 return 1
52}
53func copy_scheme(sU: *i64, sV: *i64, sW: *i64, dU: *i64, dV: *i64, dW: *i64, R: i64) -> i64 { var i: i64=0; while i<R { dU[i]=sU[i]; dV[i]=sV[i]; dW[i]=sW[i]; i=i+1 } return 0 }
54
55func reduce_pass(U: *i64, V: *i64, W: *i64, rp: *i64) -> i64 {
56 var changed: i64=1
57 while changed==1 {
58 changed=0
59 var i: i64=0
60 while i<rp[0] {
61 var zero: i64=0
62 if U[i]==0 { zero=1 }
63 if V[i]==0 { zero=1 }
64 if W[i]==0 { zero=1 }
65 if zero==1 { let L: i64=rp[0]-1; U[i]=U[L]; V[i]=V[L]; W[i]=W[L]; rp[0]=L; changed=1 } else { i=i+1 }
66 }
67 var a: i64=0
68 while a<rp[0] {
69 var b: i64=a+1; var cancelled: i64=0
70 while b<rp[0] {
71 var same: i64=0
72 if U[a]==U[b] { if V[a]==V[b] { if W[a]==W[b] { same=1 } } }
73 if same==1 {
74 let L1: i64=rp[0]-1; U[b]=U[L1]; V[b]=V[L1]; W[b]=W[L1]; rp[0]=L1
75 let L2: i64=rp[0]-1; U[a]=U[L2]; V[a]=V[L2]; W[a]=W[L2]; rp[0]=L2
76 cancelled=1; changed=1; b=rp[0]
77 } else { b=b+1 }
78 }
79 if cancelled==1 { a=0 } else { a=a+1 }
80 }
81 }
82 return 0
83}
84func do_flip(U: *i64, V: *i64, W: *i64, rp: *i64, st: *i64, cand: *i64) -> i64 {
85 let R: i64=rp[0]
86 if R<2 { return 0 }
87 let slot: i64 = rpos(st)%3
88 let i: i64 = rpos(st)%R
89 var cnt: i64=0; var jj: i64=0
90 while jj<R {
91 if jj!=i {
92 var same: i64=0
93 if slot==0 { if U[jj]==U[i] { same=1 } }
94 if slot==1 { if V[jj]==V[i] { same=1 } }
95 if slot==2 { if W[jj]==W[i] { same=1 } }
96 if same==1 { cand[cnt]=jj; cnt=cnt+1 }
97 }
98 jj=jj+1
99 }
100 if cnt==0 { return 0 }
101 let j: i64 = cand[rpos(st)%cnt]
102 if slot==0 { let v1: i64=V[i]; let w1: i64=W[i]; let v2: i64=V[j]; let w2: i64=W[j]; W[i]=w1^w2; V[j]=v1^v2 }
103 if slot==1 { let u1: i64=U[i]; let w1: i64=W[i]; let u2: i64=U[j]; let w2: i64=W[j]; W[i]=w1^w2; U[j]=u1^u2 }
104 if slot==2 { let u1: i64=U[i]; let v1: i64=V[i]; let u2: i64=U[j]; let v2: i64=V[j]; V[i]=v1^v2; U[j]=u1^u2 }
105 return 0
106}
107func run_search(m: i64, n: i64, p: i64, da: i64, db: i64, dc: i64, t: *i64, bU: *i64, bV: *i64, bW: *i64, brp: *i64, seed: i64, steps: i64, target: i64) -> i64 {
108 let U: *i64=sys_mmap(8*64) as *i64; let V: *i64=sys_mmap(8*64) as *i64; let W: *i64=sys_mmap(8*64) as *i64
109 let rp: *i64=sys_mmap(8) as *i64; rp[0]=build_naive(U,V,W,m,n,p)
110 let st: *i64=sys_mmap(8) as *i64; st[0]=seed
111 let cand: *i64=sys_mmap(8*64) as *i64
112 var best: i64=rp[0]; copy_scheme(U,V,W,bU,bV,bW,rp[0]); brp[0]=rp[0]
113 var step: i64=0
114 while step<steps {
115 do_flip(U,V,W,rp,st,cand)
116 reduce_pass(U,V,W,rp)
117 if rp[0]<best { best=rp[0]; copy_scheme(U,V,W,bU,bV,bW,rp[0]); brp[0]=rp[0] }
118 if rp[0]<=target { step=steps } else { step=step+1 }
119 }
120 return best
121}
122// search across seeds; returns best rank found, leaves best scheme in dU/dV/dW with discR.
123func discover(m: i64, n: i64, p: i64, da: i64, db: i64, dc: i64, t: *i64, dU: *i64, dV: *i64, dW: *i64, drp: *i64, steps: i64, target: i64, nseeds: i64) -> i64 {
124 let bU: *i64=sys_mmap(8*64) as *i64; let bV: *i64=sys_mmap(8*64) as *i64; let bW: *i64=sys_mmap(8*64) as *i64; let brp: *i64=sys_mmap(8) as *i64
125 let seeds: *i64=sys_mmap(8*32) as *i64
126 seeds[0]=0x9E3779B97F4A7C15; seeds[1]=0x2545F4914F6CDD1D; seeds[2]=0xD1B54A32D192ED03; seeds[3]=0xA0761D6478BD642F
127 seeds[4]=0xE7037ED1A0B428DB; seeds[5]=0x8EBC6AF09C88C6E3; seeds[6]=0x589965CC75374CC3; seeds[7]=0x1D8E4E27C47D124F
128 seeds[8]=0x27D4EB2F165667C5; seeds[9]=0x94D049BB133111EB; seeds[10]=0xBF58476D1CE4E5B9; seeds[11]=0x4CF5AD432745937F
129 seeds[12]=0xFF51AFD7ED558CCD; seeds[13]=0xC4CEB9FE1A85EC53; seeds[14]=0x9E6C63D0676A9A99; seeds[15]=0x2545F4914F6CDD11
130 var bestAll: i64=99; var si: i64=0
131 while si<nseeds {
132 run_search(m,n,p,da,db,dc,t, bU,bV,bW, brp, seeds[si], steps, target)
133 if brp[0]<bestAll { bestAll=brp[0]; copy_scheme(bU,bV,bW,dU,dV,dW,brp[0]); drp[0]=brp[0] }
134 if bestAll<=target { si=nseeds } else { si=si+1 }
135 }
136 return bestAll
137}
138
139func main() -> i64 {
140 let pass: *i64 = sys_mmap(8) as *i64; pass[0]=0
141 g_w("=== NX-RESEARCH-FLIP-SCALE GATE (does the flip-graph discoverer scale: <2,2,2>->7 AND <2,2,3>->11) ===\n")
142
143 // ---- <2,2,2> anchor ----
144 let t1: *i64=sys_mmap(8*512) as *i64; build_t(t1,2,2,2)
145 let nU: *i64=sys_mmap(8*64) as *i64; let nV: *i64=sys_mmap(8*64) as *i64; let nW: *i64=sys_mmap(8*64) as *i64
146 let Rn1: i64=build_naive(nU,nV,nW,2,2,2); let bn1: i64=brent_gf2(nU,nV,nW,Rn1,t1,4,4,4)
147 let d1U: *i64=sys_mmap(8*64) as *i64; let d1V: *i64=sys_mmap(8*64) as *i64; let d1W: *i64=sys_mmap(8*64) as *i64; let drp1: *i64=sys_mmap(8) as *i64
148 let r222: i64=discover(2,2,2,4,4,4,t1, d1U,d1V,d1W,drp1, 60000, 7, 8)
149 let bd1: i64=brent_gf2(d1U,d1V,d1W,drp1[0],t1,4,4,4)
150
151 // ---- <2,2,3> scale-up: naive 12, optimum 11 ----
152 let t2: *i64=sys_mmap(8*512) as *i64; build_t(t2,2,2,3)
153 let nU2: *i64=sys_mmap(8*64) as *i64; let nV2: *i64=sys_mmap(8*64) as *i64; let nW2: *i64=sys_mmap(8*64) as *i64
154 let Rn2: i64=build_naive(nU2,nV2,nW2,2,2,3); let bn2: i64=brent_gf2(nU2,nV2,nW2,Rn2,t2,4,6,6)
155 let d2U: *i64=sys_mmap(8*64) as *i64; let d2V: *i64=sys_mmap(8*64) as *i64; let d2W: *i64=sys_mmap(8*64) as *i64; let drp2: *i64=sys_mmap(8) as *i64
156 let r223: i64=discover(2,2,3,4,6,6,t2, d2U,d2V,d2W,drp2, 500000, 11, 16)
157 let bd2: i64=brent_gf2(d2U,d2V,d2W,drp2[0],t2,4,6,6)
158
159 // liar-kill on the <2,2,3> discovery
160 let xU: *i64=sys_mmap(8*64) as *i64; let xV: *i64=sys_mmap(8*64) as *i64; let xW: *i64=sys_mmap(8*64) as *i64
161 copy_scheme(d2U,d2V,d2W,xU,xV,xW,drp2[0]); xW[0]=xW[0]^1
162 let bk: i64=(brent_gf2(xU,xV,xW,drp2[0],t2,4,6,6)==0) as i64
163
164 g_w(" <2,2,2>: naive rank="); g_n(Rn1); g_w(" brent="); g_n(bn1); g_w(" DISCOVERED rank="); g_n(r222); g_w(" brent="); g_n(bd1); g_w("\n")
165 g_w(" <2,2,3>: naive rank="); g_n(Rn2); g_w(" brent="); g_n(bn2); g_w(" DISCOVERED rank="); g_n(r223); g_w(" brent="); g_n(bd2); g_w("\n")
166
167 g_row("ANCHOR <2,2,2>: generalized engine re-discovers rank-7 from naive 8 (Brent-valid)" as *u8, ((r222==7) as i64)*bd1, pass)
168 g_row("SETUP <2,2,3>: naive rank-12 scheme verifies over GF(2) (generalized tensor+builder correct)" as *u8, bn2, pass)
169 var sc: i64=0; if r223<=11 { if r223<Rn2 { sc=1 } }
170 g_row("SCALE-UP <2,2,3>: flip-graph discovers a rank reduction to 11 (12->11, Hopcroft-Kerr optimum)" as *u8, sc, pass)
171 g_row("VERIFY <2,2,3>: the discovered scheme is Brent-valid over GF(2) (computes 2x2*2x3 exactly)" as *u8, bd2, pass)
172 var meas: i64=0; if r222<Rn1 { if r223<Rn2 { meas=1 } }
173 g_row("MEASURED: rank reductions in TWO distinct shapes (7<8 AND 11<12), one sovereign engine" as *u8, meas, pass)
174 g_row("HONEST SCOPE: 7 and 11 are proven optima (cited); discovered by local search, no record claim" as *u8, ((r222==7) as i64)*((r223==11) as i64), pass)
175 g_row("LIAR-KILL: a broken <2,2,3> scheme (one bit flipped) is REJECTED by the Brent verifier" as *u8, bk, pass)
176
177 g_w("RESEARCH-FLIP-SCALE-GATE rows=7 pass="); g_n(pass[0])
178 if pass[0]==7 { g_w(" verdict=GREEN\n"); sys_exit(0); return 0 }
179 g_w(" verdict=RED\n"); sys_exit(1); return 1
180}