nx_research_strassen4_gate.nx source

1// nx_research_strassen4_gate.nx -- from REPRODUCTION toward DISCOVERY: show WHY finding low-multiplication 2// schemes matters. Strassen's 2x2 saving (7 mults instead of 8) COMPOUNDS recursively: a 4x4 product done by 3// block-Strassen (2x2 blocks of 2x2 blocks) costs 7x7 = 49 scalar multiplications instead of the naive 4^3 = 64. 4// The TESTING-TEAM runs both, proves block-Strassen == naive bit-exact (independent KAT A*I=A and I*B=B, plus 5// random matrices), COUNTS the multiplications (49 vs 64 = the compounding payoff), and the VERIFIER liar-kill 6// rejects a deliberately-broken recursive scheme. This is the substrate an alphatensor-class search rides on: 7// a candidate scheme is only "discovered" once this exact-comparison gate certifies it. Exact integer, no float, 8// deterministic. GREEN iff 6/6. license_tier: ORIGINAL 9import "nx_syscalls.nx" 10 11func 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 } 12func 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 } 13func 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 } 14 15func rs_mul(cnt: *i64, a: i64, b: i64) -> i64 { cnt[0] = cnt[0] + 1; return a * b } 16func rs_rng(state: *i64) -> i64 { var x: i64 = state[0]; x = x ^ (x << 13); x = x ^ (x >> 7); x = x ^ (x << 17); state[0] = x; return x } 17 18// ---- 2x2 block primitives (blocks are [00,01,10,11]) ---- 19func bl_add(x: *i64, y: *i64, o: *i64) -> i64 { o[0]=x[0]+y[0]; o[1]=x[1]+y[1]; o[2]=x[2]+y[2]; o[3]=x[3]+y[3]; return 0 } 20func bl_sub(x: *i64, y: *i64, o: *i64) -> i64 { o[0]=x[0]-y[0]; o[1]=x[1]-y[1]; o[2]=x[2]-y[2]; o[3]=x[3]-y[3]; return 0 } 21// 2x2 Strassen multiply: 7 scalar multiplications (counted). 22func bl_strassen(x: *i64, y: *i64, o: *i64, cnt: *i64) -> i64 { 23 let m1: i64 = rs_mul(cnt, x[0]+x[3], y[0]+y[3]) 24 let m2: i64 = rs_mul(cnt, x[2]+x[3], y[0]) 25 let m3: i64 = rs_mul(cnt, x[0], y[1]-y[3]) 26 let m4: i64 = rs_mul(cnt, x[3], y[2]-y[0]) 27 let m5: i64 = rs_mul(cnt, x[0]+x[1], y[3]) 28 let m6: i64 = rs_mul(cnt, x[2]-x[0], y[0]+y[1]) 29 let m7: i64 = rs_mul(cnt, x[1]-x[3], y[2]+y[3]) 30 o[0] = m1 + m4 - m5 + m7; o[1] = m3 + m5; o[2] = m2 + m4; o[3] = m1 - m2 + m3 + m6 31 return 0 32} 33 34// a slice of the scratch arena: the i-th 2x2 block (4 i64 = 32 bytes). 35func blk(sc: *i64, i: i64) -> *i64 { return ((sc as i64) + i*32) as *i64 } 36// extract / write a 2x2 block (br,bc in {0,1}) of a row-major 4x4 (16 i64). 37func get_block(m16: *i64, br: i64, bc: i64, out: *i64) -> i64 { 38 let r0: i64 = br*2; let c0: i64 = bc*2 39 out[0]=m16[r0*4+c0]; out[1]=m16[r0*4+c0+1]; out[2]=m16[(r0+1)*4+c0]; out[3]=m16[(r0+1)*4+c0+1]; return 0 40} 41func set_block(m16: *i64, br: i64, bc: i64, b: *i64) -> i64 { 42 let r0: i64 = br*2; let c0: i64 = bc*2 43 m16[r0*4+c0]=b[0]; m16[r0*4+c0+1]=b[1]; m16[(r0+1)*4+c0]=b[2]; m16[(r0+1)*4+c0+1]=b[3]; return 0 44} 45 46// naive 4x4 matmul: 4^3 = 64 scalar multiplications. 47func mm4_naive(a: *i64, b: *i64, c: *i64, cnt: *i64) -> i64 { 48 var i: i64=0 49 while i<4 { var j: i64=0; while j<4 { var s: i64=0; var k: i64=0; while k<4 { s = s + rs_mul(cnt, a[i*4+k], b[k*4+j]); k=k+1 } c[i*4+j]=s; j=j+1 } i=i+1 } 50 return 0 51} 52// block-Strassen 4x4 matmul: 7 block-multiplies x 7 = 49 scalar multiplications. `bad`=1 corrupts C11 (liar-kill). 53func mm4_strassen(a: *i64, b: *i64, c: *i64, cnt: *i64, sc: *i64, bad: i64) -> i64 { 54 let A00: *i64=blk(sc,0); let A01: *i64=blk(sc,1); let A10: *i64=blk(sc,2); let A11: *i64=blk(sc,3) 55 let B00: *i64=blk(sc,4); let B01: *i64=blk(sc,5); let B10: *i64=blk(sc,6); let B11: *i64=blk(sc,7) 56 get_block(a,0,0,A00); get_block(a,0,1,A01); get_block(a,1,0,A10); get_block(a,1,1,A11) 57 get_block(b,0,0,B00); get_block(b,0,1,B01); get_block(b,1,0,B10); get_block(b,1,1,B11) 58 let M1: *i64=blk(sc,8); let M2: *i64=blk(sc,9); let M3: *i64=blk(sc,10); let M4: *i64=blk(sc,11) 59 let M5: *i64=blk(sc,12); let M6: *i64=blk(sc,13); let M7: *i64=blk(sc,14) 60 let t1: *i64=blk(sc,15); let t2: *i64=blk(sc,16); let tt: *i64=blk(sc,17) 61 bl_add(A00,A11,t1); bl_add(B00,B11,t2); bl_strassen(t1,t2,M1,cnt) 62 bl_add(A10,A11,t1); bl_strassen(t1,B00,M2,cnt) 63 bl_sub(B01,B11,t2); bl_strassen(A00,t2,M3,cnt) 64 bl_sub(B10,B00,t2); bl_strassen(A11,t2,M4,cnt) 65 bl_add(A00,A01,t1); bl_strassen(t1,B11,M5,cnt) 66 bl_sub(A10,A00,t1); bl_add(B00,B01,t2); bl_strassen(t1,t2,M6,cnt) 67 bl_sub(A01,A11,t1); bl_add(B10,B11,t2); bl_strassen(t1,t2,M7,cnt) 68 let C00: *i64=blk(sc,18); let C01: *i64=blk(sc,19); let C10: *i64=blk(sc,20); let C11: *i64=blk(sc,21) 69 bl_add(M1,M4,tt); bl_sub(tt,M5,tt); bl_add(tt,M7,C00) 70 bl_add(M3,M5,C01) 71 bl_add(M2,M4,C10) 72 if bad==1 { bl_add(M1,M2,tt) } else { bl_sub(M1,M2,tt) } // bad: +M2 instead of -M2 73 bl_add(tt,M3,tt); bl_add(tt,M6,C11) 74 set_block(c,0,0,C00); set_block(c,0,1,C01); set_block(c,1,0,C10); set_block(c,1,1,C11) 75 return 0 76} 77func eq16(x: *i64, y: *i64) -> i64 { var i: i64=0; while i<16 { if x[i]!=y[i]{return 0} i=i+1 } return 1 } 78 79func main() -> i64 { 80 let pass: *i64 = sys_mmap(8) as *i64; pass[0] = 0 81 g_w("=== NX-RESEARCH-STRASSEN4 GATE (recursive Strassen: 4x4 in 49 mults vs naive 64) ===\n") 82 let sc: *i64 = sys_mmap(4096) as *i64 83 let dump: *i64 = sys_mmap(8) as *i64 84 85 // KAT 1: A * I = A (A = [1..16], I = 4x4 identity) 86 let A: *i64 = sys_mmap(256) as *i64; var i: i64=0; while i<16 { A[i]=i+1; i=i+1 } 87 let I: *i64 = sys_mmap(256) as *i64; i=0; while i<16 { I[i]=0; i=i+1 } I[0]=1; I[5]=1; I[10]=1; I[15]=1 88 let R: *i64 = sys_mmap(256) as *i64 89 dump[0]=0; mm4_strassen(A, I, R, dump, sc, 0) 90 let kat1: i64 = eq16(R, A) 91 // KAT 2: I * B = B 92 let B: *i64 = sys_mmap(256) as *i64; i=0; while i<16 { B[i]=(i*3+1); i=i+1 } 93 dump[0]=0; mm4_strassen(I, B, R, dump, sc, 0) 94 let kat2: i64 = eq16(R, B) 95 96 // reproducibility: block-Strassen == naive over N random 4x4 97 let st: *i64 = sys_mmap(8) as *i64; st[0] = 0x9E3779B97F4A7C15 98 let ra: *i64 = sys_mmap(256) as *i64; let rb: *i64 = sys_mmap(256) as *i64 99 let r1: *i64 = sys_mmap(256) as *i64; let r2: *i64 = sys_mmap(256) as *i64 100 var iter: i64=0; var mism: i64=0; let N: i64=200 101 while iter<N { 102 i=0; while i<16 { ra[i]=(rs_rng(st) & 0xf) - 8; i=i+1 } 103 i=0; while i<16 { rb[i]=(rs_rng(st) & 0xf) - 8; i=i+1 } 104 dump[0]=0; mm4_naive(ra, rb, r1, dump) 105 dump[0]=0; mm4_strassen(ra, rb, r2, dump, sc, 0) 106 if eq16(r1, r2)==0 { mism=mism+1 } 107 iter=iter+1 108 } 109 110 // counts 111 let cn: *i64 = sys_mmap(8) as *i64; cn[0]=0; mm4_naive(A, B, R, cn); let mulsN: i64=cn[0] 112 let cs: *i64 = sys_mmap(8) as *i64; cs[0]=0; mm4_strassen(A, B, R, cs, sc, 0); let mulsS: i64=cs[0] 113 114 // liar-kill: broken recursive scheme != naive 115 dump[0]=0; mm4_naive(A, B, r1, dump) 116 dump[0]=0; mm4_strassen(A, B, r2, dump, sc, 1) 117 let broken_caught: i64 = (eq16(r1, r2)==0) as i64 118 119 g_w(" KAT A*I==A="); g_n(kat1); g_w(" I*B==B="); g_n(kat2); g_w("\n") 120 g_w(" reproducibility: "); g_n(N); g_w(" random 4x4, block-Strassen!=naive mismatches="); g_n(mism); g_w("\n") 121 g_w(" multiplications: naive="); g_n(mulsN); g_w(" recursive-Strassen="); g_n(mulsS); g_w(" (7x7 vs 4^3)\n") 122 123 g_row("KAT: block-Strassen reproduces A*I = A (independent known answer)" as *u8, kat1, pass) 124 g_row("KAT: block-Strassen reproduces I*B = B" as *u8, kat2, pass) 125 g_row("REPRODUCIBILITY: block-Strassen == naive over 200 random 4x4 (0 mismatch)" as *u8, (mism==0) as i64, pass) 126 g_row("EFFICIENCY: naive 4x4 uses 64 scalar multiplications (counted)" as *u8, (mulsN==64) as i64, pass) 127 g_row("COMPOUNDING: recursive Strassen uses 49 = 7^2 (the 7-for-8 saving compounds)" as *u8, (mulsS==49) as i64, pass) 128 g_row("LIAR-KILL: a broken recursive scheme is REJECTED by exact comparison" as *u8, broken_caught, pass) 129 130 g_w("STRASSEN4-GATE rows=6 pass="); g_n(pass[0]) 131 if pass[0] == 6 { g_w(" verdict=GREEN\n"); sys_exit(0); return 0 } 132 g_w(" verdict=RED\n"); sys_exit(1); return 1 133}