code wiki / _hdl_build / nx_research_flip_discover_gate.nx
nx_research_flip_discover_gate.nx source
↩ module page · 214 lines · 12083 B
1// nx_research_flip_discover_gate.nx -- the FLAGSHIP discovery: genuinely DISCOVER a faster matrix-multiplication
2// scheme by SEARCH (not certify a supplied one), the modern AlphaTensor-class method done sovereignly.
3//
4// Exhaustive search can't reach Strassen's rank-7 for <2,2,2> (the coefficient space is astronomical). The
5// FLIP-GRAPH local search (Kauers & Moosbauer 2022 -- how recent matmul rank records were set WITHOUT RL) can:
6// a decomposition of the matmul tensor T over GF(2) is a multiset of rank-1 triples (u_r,v_r,w_r) summing to T.
7// FLIP : two triples sharing one factor, e.g. (a,v1,w1)+(a,v2,w2) = (a,v1,w1+w2)+(a,v1+v2,w2) over GF(2)
8// -- rank-preserving (2 terms -> 2 terms), a random-walk neighbor.
9// REDUCE : when a flip makes a factor 0 (term vanishes) or two triples coincide (cancel over GF(2)), the
10// rank DROPS. Flips never raise rank, reductions only lower it -> rank is monotone non-increasing,
11// so the walk only needs to find ONE 8->7 reduction (easy for <2,2,2>; 6 is impossible -> floor 7).
12// Start from the naive rank-8 scheme, random-walk with a deterministic PRNG until rank 7 is DISCOVERED, then the
13// Brent-equation verifier (over GF(2)) certifies the discovered scheme computes <2,2,2> exactly + a random-input
14// cross-check. LIAR-KILL: a broken scheme is rejected. HONEST SCOPE: 7 is the proven optimum for 2x2
15// (Hopcroft-Kerr/Winograd, cited); we discover it sovereignly -- we do NOT claim AlphaTensor's larger records.
16// GREEN iff 7/7. license_tier: ORIGINAL
17import "nx_syscalls.nx"
18
19func 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 }
20func 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 }
21func 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 }
22
23func bitof(x: i64, i: i64) -> i64 { return (x>>i)&1 }
24func 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 }
25func rpos(s: *i64) -> i64 { let v: i64 = xrng(s); return v & 0x3FFFFFFFFFFFFFFF }
26
27// <2,2,2> matmul tensor over GF(2): index ((i*4+j)*4+k); a=(p,q)=i, b=(r,s)=j, c=(x,y)=k; 1 iff x==p,q==r,s==y.
28func build_t(t: *i64) -> i64 {
29 var a: i64=0
30 while a<4 { let p: i64=a/2; let q: i64=a%2; var b: i64=0
31 while b<4 { let r: i64=b/2; let s: i64=b%2; var c: i64=0
32 while c<4 { let x: i64=c/2; let yy: i64=c%2; var val: i64=0
33 if x==p { if q==r { if s==yy { val=1 } } }
34 t[(a*4+b)*4+c]=val; c=c+1 }
35 b=b+1 }
36 a=a+1 }
37 return 0
38}
39// naive rank-8: one product per (x,m,y); u=e_{x*2+m}, v=e_{m*2+y}, w=e_{x*2+y}.
40func build_naive(U: *i64, V: *i64, W: *i64) -> i64 {
41 var idx: i64=0; var x: i64=0
42 while x<2 { var m: i64=0
43 while m<2 { var y: i64=0
44 while y<2 { U[idx]=1<<(x*2+m); V[idx]=1<<(m*2+y); W[idx]=1<<(x*2+y); idx=idx+1; y=y+1 }
45 m=m+1 }
46 x=x+1 }
47 return 8
48}
49// Brent over GF(2): for all i,j,k, XOR_r u_r[i]&v_r[j]&w_r[k] == T[i][j][k].
50func brent_gf2(U: *i64, V: *i64, W: *i64, R: i64, t: *i64) -> i64 {
51 var i: i64=0
52 while i<4 { var j: i64=0
53 while j<4 { var k: i64=0
54 while k<4 {
55 var acc: i64=0; var r: i64=0
56 while r<R { acc = acc ^ (bitof(U[r],i) & bitof(V[r],j) & bitof(W[r],k)); r=r+1 }
57 if acc != t[(i*4+j)*4+k] { return 0 }
58 k=k+1 }
59 j=j+1 }
60 i=i+1 }
61 return 1
62}
63func 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 }
64
65// drop zero-factor terms + cancel coincident pairs (the rank reductions) until stable.
66func reduce_pass(U: *i64, V: *i64, W: *i64, rp: *i64) -> i64 {
67 var changed: i64=1
68 while changed==1 {
69 changed=0
70 var i: i64=0
71 while i<rp[0] {
72 var zero: i64=0
73 if U[i]==0 { zero=1 }
74 if V[i]==0 { zero=1 }
75 if W[i]==0 { zero=1 }
76 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 }
77 }
78 var a: i64=0
79 while a<rp[0] {
80 var b: i64=a+1; var cancelled: i64=0
81 while b<rp[0] {
82 var same: i64=0
83 if U[a]==U[b] { if V[a]==V[b] { if W[a]==W[b] { same=1 } } }
84 if same==1 {
85 let L1: i64=rp[0]-1; U[b]=U[L1]; V[b]=V[L1]; W[b]=W[L1]; rp[0]=L1
86 let L2: i64=rp[0]-1; U[a]=U[L2]; V[a]=V[L2]; W[a]=W[L2]; rp[0]=L2
87 cancelled=1; changed=1; b=rp[0]
88 } else { b=b+1 }
89 }
90 if cancelled==1 { a=0 } else { a=a+1 }
91 }
92 }
93 return 0
94}
95// one random flip: pick a slot + a pair sharing that slot, apply the GF(2) rewrite to the other two slots.
96func do_flip(U: *i64, V: *i64, W: *i64, rp: *i64, st: *i64, cand: *i64) -> i64 {
97 let R: i64=rp[0]
98 if R<2 { return 0 }
99 let slot: i64 = rpos(st)%3
100 let i: i64 = rpos(st)%R
101 var cnt: i64=0; var jj: i64=0
102 while jj<R {
103 if jj!=i {
104 var same: i64=0
105 if slot==0 { if U[jj]==U[i] { same=1 } }
106 if slot==1 { if V[jj]==V[i] { same=1 } }
107 if slot==2 { if W[jj]==W[i] { same=1 } }
108 if same==1 { cand[cnt]=jj; cnt=cnt+1 }
109 }
110 jj=jj+1
111 }
112 if cnt==0 { return 0 }
113 let j: i64 = cand[rpos(st)%cnt]
114 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 }
115 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 }
116 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 }
117 return 0
118}
119// one seeded flip-graph walk from naive; tracks the best (lowest-rank) scheme into bU/bV/bW/brp.
120func run_search(t: *i64, bU: *i64, bV: *i64, bW: *i64, brp: *i64, seed: i64, steps: i64) -> i64 {
121 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
122 let rp: *i64=sys_mmap(8) as *i64; rp[0]=build_naive(U,V,W)
123 let st: *i64=sys_mmap(8) as *i64; st[0]=seed
124 let cand: *i64=sys_mmap(8*64) as *i64
125 var best: i64=rp[0]; copy_scheme(U,V,W,bU,bV,bW,rp[0]); brp[0]=rp[0]
126 var step: i64=0
127 while step<steps {
128 do_flip(U,V,W,rp,st,cand)
129 reduce_pass(U,V,W,rp)
130 if rp[0]<best { best=rp[0]; copy_scheme(U,V,W,bU,bV,bW,rp[0]); brp[0]=rp[0] }
131 if rp[0]<=7 { step=steps } else { step=step+1 }
132 }
133 return best
134}
135// independent functional cross-check: scheme reproduces A*B over random GF(2) 2x2 inputs.
136func mm_verify_gf2(U: *i64, V: *i64, W: *i64, R: i64, st: *i64) -> i64 {
137 let a: *i64=sys_mmap(8*8) as *i64; let b: *i64=sys_mmap(8*8) as *i64
138 let cN: *i64=sys_mmap(8*8) as *i64; let cS: *i64=sys_mmap(8*8) as *i64
139 var it: i64=0; var mism: i64=0
140 while it<64 {
141 var z: i64=0; while z<4 { a[z]=rpos(st)&1; b[z]=rpos(st)&1; z=z+1 }
142 var x: i64=0; while x<2 { var y: i64=0; while y<2 { var acc: i64=0; var m: i64=0; while m<2 { acc=acc^(a[x*2+m]&b[m*2+y]); m=m+1 } cN[x*2+y]=acc; y=y+1 } x=x+1 }
143 var k: i64=0; while k<4 { cS[k]=0; k=k+1 }
144 var r: i64=0
145 while r<R {
146 var la: i64=0; var i: i64=0; while i<4 { la=la^(bitof(U[r],i)&a[i]); i=i+1 }
147 var lb: i64=0; var j: i64=0; while j<4 { lb=lb^(bitof(V[r],j)&b[j]); j=j+1 }
148 let mr: i64=la&lb
149 k=0; while k<4 { cS[k]=cS[k]^(bitof(W[r],k)&mr); k=k+1 }
150 r=r+1
151 }
152 k=0; while k<4 { if cN[k]!=cS[k] { mism=mism+1 } k=k+1 }
153 it=it+1
154 }
155 return (mism==0) as i64
156}
157
158func main() -> i64 {
159 let pass: *i64 = sys_mmap(8) as *i64; pass[0]=0
160 g_w("=== NX-RESEARCH-FLIP-DISCOVER GATE (flagship: DISCOVER Strassen rank-7 by sovereign flip-graph search) ===\n")
161 let t: *i64=sys_mmap(8*64) as *i64; build_t(t)
162
163 // row1: naive rank-8 verifies over GF(2)
164 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
165 let Rn: i64=build_naive(nU,nV,nW); let bn: i64=brent_gf2(nU,nV,nW,Rn,t)
166
167 // row2: flip-invariant -- 20 flips (no reduce) keep the scheme == T
168 let fU: *i64=sys_mmap(8*64) as *i64; let fV: *i64=sys_mmap(8*64) as *i64; let fW: *i64=sys_mmap(8*64) as *i64
169 copy_scheme(nU,nV,nW,fU,fV,fW,8); let frp: *i64=sys_mmap(8) as *i64; frp[0]=8
170 let fst: *i64=sys_mmap(8) as *i64; fst[0]=0x1111111111111111; let fcand: *i64=sys_mmap(8*64) as *i64
171 var fk: i64=0; while fk<20 { do_flip(fU,fV,fW,frp,fst,fcand); fk=fk+1 }
172 let binv: i64=brent_gf2(fU,fV,fW,frp[0],t)
173
174 // DISCOVERY: flip-graph search across seeds until rank-7 found
175 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
176 let dU: *i64=sys_mmap(8*64) as *i64; let dV: *i64=sys_mmap(8*64) as *i64; let dW: *i64=sys_mmap(8*64) as *i64
177 var discR: i64=99; var usedSeed: i64=0
178 let seeds: *i64=sys_mmap(8*32) as *i64
179 seeds[0]=0x9E3779B97F4A7C15; seeds[1]=0x2545F4914F6CDD1D; seeds[2]=0xD1B54A32D192ED03; seeds[3]=0xA0761D6478BD642F
180 seeds[4]=0xE7037ED1A0B428DB; seeds[5]=0x8EBC6AF09C88C6E3; seeds[6]=0x589965CC75374CC3; seeds[7]=0x1D8E4E27C47D124F
181 var si: i64=0
182 while si<8 {
183 let r: i64=run_search(t, bU,bV,bW, brp, seeds[si], 40000)
184 g_w(" seed#"); g_n(si); g_w(" best_rank="); g_n(brp[0]); g_w("\n")
185 if brp[0]<discR { discR=brp[0]; copy_scheme(bU,bV,bW,dU,dV,dW,brp[0]); usedSeed=si }
186 if discR<=7 { si=8 } else { si=si+1 }
187 }
188
189 let bd: i64=brent_gf2(dU,dV,dW,discR,t)
190 let st2: *i64=sys_mmap(8) as *i64; st2[0]=0x123456789ABCDEF
191 let mm: i64=mm_verify_gf2(dU,dV,dW,discR,st2)
192 // liar-kill: flip one bit of the discovered scheme -> must fail Brent
193 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
194 copy_scheme(dU,dV,dW,xU,xV,xW,discR); xW[0]=xW[0]^1
195 let bk: i64=(brent_gf2(xU,xV,xW,discR,t)==0) as i64
196
197 g_w(" naive rank="); g_n(Rn); g_w(" brent="); g_n(bn); g_w(" flip-invariant brent="); g_n(binv); g_w("\n")
198 g_w(" DISCOVERED rank="); g_n(discR); g_w(" (seed#"); g_n(usedSeed); g_w(") brent="); g_n(bd); g_w(" matmul-over-random="); g_n(mm); g_w("\n")
199 if discR<=8 { g_w(" scheme:"); var q: i64=0; while q<discR { g_w(" ("); g_n(dU[q]); g_w(","); g_n(dV[q]); g_w(","); g_n(dW[q]); g_w(")"); q=q+1 } g_w("\n") }
200
201 g_row("VERIFIER(GF2): Brent certifies the naive <2,2,2> rank-8 scheme computes matmul exactly" as *u8, bn, pass)
202 g_row("FLIP-INVARIANT: 20 random flips preserve correctness (scheme still == T)" as *u8, binv, pass)
203 g_row("DISCOVERY: flip-graph search from naive rank-8 discovers a rank-7 scheme (8->7)" as *u8, (discR==7) as i64, pass)
204 var ver: i64=0; if bd==1 { if mm==1 { ver=1 } }
205 g_row("VERIFY: discovered rank-7 is Brent-valid AND reproduces 2x2 matmul over random GF(2) inputs" as *u8, ver, pass)
206 var meas: i64=0; if discR==7 { if discR<Rn { meas=1 } }
207 g_row("MEASURED: rank 7 < naive 8 (Strassen-class saving) discovered sovereignly via flip graph, no RL" as *u8, meas, pass)
208 g_row("HONEST SCOPE: 7 is the proven 2x2 optimum (cited); discovered by local search, not an AlphaTensor-record claim" as *u8, (discR==7) as i64, pass)
209 g_row("LIAR-KILL: a broken scheme (one bit flipped) is REJECTED by the Brent verifier" as *u8, bk, pass)
210
211 g_w("RESEARCH-FLIP-DISCOVER-GATE rows=7 pass="); g_n(pass[0])
212 if pass[0]==7 { g_w(" verdict=GREEN\n"); sys_exit(0); return 0 }
213 g_w(" verdict=RED\n"); sys_exit(1); return 1
214}