nx_research_isqrt_gate.nx source

1// nx_research_isqrt_gate.nx -- sovereign integer square root: Newton's method ITERATIVELY DISCOVERS floor(sqrt(N)), 2// and an exact integer bracketing check (r^2 <= N < (r+1)^2) VERIFIES it -- the discover-then-verify pattern, and 3// a foundational primitive (unblocks 1/r^2 force laws for orbital dynamics). MEASURED: Newton converges in a 4// handful of iterations where a naive linear scan needs O(sqrt(N)). Liar-kill: a wrong root fails the bracket. 5// Pure integer, deterministic. GREEN iff 6/6. license_tier: ORIGINAL 6import "nx_syscalls.nx" 7 8func 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 } 9func 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 } 10func 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 } 11func 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 } 12func rpos(s: *i64) -> i64 { let v: i64 = xrng(s); return v & 0x3FFFFFFFFFFFFFFF } 13 14// Newton's method for floor(sqrt(N)); writes the iteration count to itp. 15func isqrt(N: i64, itp: *i64) -> i64 { 16 if N<2 { itp[0]=0; return N } 17 var x: i64=N; var y: i64=(x+1)/2; var it: i64=1 18 while y<x { x=y; y=(x + N/x)/2; it=it+1 } 19 itp[0]=it 20 return x 21} 22// naive linear scan (the O(sqrt(N)) baseline), iteration-counted. 23func isqrt_naive(N: i64, itp: *i64) -> i64 { 24 var r: i64=0; var it: i64=0 25 while (r+1)*(r+1) <= N { r=r+1; it=it+1 } 26 itp[0]=it 27 return r 28} 29// the VERIFIER: r is exactly floor(sqrt(N)) iff r^2 <= N < (r+1)^2. 30func bracket_ok(N: i64, r: i64) -> i64 { if r*r>N { return 0 } if (r+1)*(r+1)<=N { return 0 } return 1 } 31 32func main() -> i64 { 33 let pass: *i64 = sys_mmap(8) as *i64; pass[0]=0 34 g_w("=== NX-RESEARCH-ISQRT GATE (Newton discovers floor(sqrt(N)); exact bracketing verifies) ===\n") 35 let it: *i64=sys_mmap(8) as *i64 36 37 // perfect squares 38 let s144: i64=isqrt(144,it); let s1m: i64=isqrt(1000000,it); let s1t: i64=isqrt(1000000000000,it) 39 var sq_ok: i64=0 40 if s144==12 { if s1m==1000 { if s1t==1000000 { sq_ok=1 } } } 41 // non-squares (floor) 42 let n2: i64=isqrt(2,it); let n10: i64=isqrt(10,it); let n99: i64=isqrt(99,it); let n2t: i64=isqrt(2000000000000,it) 43 var ns_ok: i64=0 44 if n2==1 { if n10==3 { if n99==9 { if n2t==1414213 { ns_ok=1 } } } } 45 // bracketing on all of the above 46 var br_ok: i64=0 47 if bracket_ok(144,s144)==1 { if bracket_ok(1000000000000,s1t)==1 { if bracket_ok(99,n99)==1 { if bracket_ok(2000000000000,n2t)==1 { br_ok=1 } } } } 48 49 // MEASURED: Newton iters vs naive iters for N=10^12 50 let itN: *i64=sys_mmap(8) as *i64; let rNewton: i64=isqrt(1000000000000, itN) 51 let itL: *i64=sys_mmap(8) as *i64; let rNaive: i64=isqrt_naive(1000000000000, itL) 52 var meas: i64=0 53 if rNewton==rNaive { if itN[0]<=40 { if itL[0]>=1000000 { meas=1 } } } 54 55 // STRESS: 1000 random N up to ~2e12, bracketing must always hold 56 let st: *i64=sys_mmap(8) as *i64; st[0]=0x9E3779B97F4A7C15 57 var i: i64=0; var viol: i64=0 58 while i<1000 { 59 let N: i64=(rpos(st)%2000000000000)+1 60 let r: i64=isqrt(N,it) 61 if bracket_ok(N,r)==0 { viol=viol+1 } 62 i=i+1 63 } 64 // liar-kill: a wrong root (r+1) must fail the bracket 65 let rg: i64=isqrt(99,it) 66 let liar: i64=(bracket_ok(99, rg+1)==0) as i64 67 68 g_w(" perfect: sqrt(144)="); g_n(s144); g_w(" sqrt(1e6)="); g_n(s1m); g_w(" sqrt(1e12)="); g_n(s1t); g_w("\n") 69 g_w(" floor: sqrt(2)="); g_n(n2); g_w(" sqrt(10)="); g_n(n10); g_w(" sqrt(99)="); g_n(n99); g_w(" sqrt(2e12)="); g_n(n2t); g_w("\n") 70 g_w(" MEASURED N=1e12: Newton iters="); g_n(itN[0]); g_w(" naive iters="); g_n(itL[0]); g_w(" (same result="); g_n((rNewton==rNaive) as i64); g_w(")\n") 71 g_w(" stress: 1000 random N, bracket violations="); g_n(viol); g_w("\n") 72 73 g_row("DISCOVERY: Newton's method computes floor(sqrt) of perfect squares (144->12, 1e6->1000, 1e12->1e6)" as *u8, sq_ok, pass) 74 g_row("FLOOR: non-squares give the exact floor (2->1, 10->3, 99->9, 2e12->1414213)" as *u8, ns_ok, pass) 75 g_row("VERIFIER: bracketing r^2 <= N < (r+1)^2 holds (the exact floor-sqrt property)" as *u8, br_ok, pass) 76 g_row("MEASURED: Newton converges in <=40 iters where naive linear needs ~1e6 (same root)" as *u8, meas, pass) 77 g_row("STRESS: bracketing holds over 1000 deterministic-random N up to 2e12 (0 violations)" as *u8, (viol==0) as i64, pass) 78 g_row("LIAR-KILL: a wrong root (r+1) is REJECTED by the bracketing verifier" as *u8, liar, pass) 79 80 g_w("RESEARCH-ISQRT-GATE rows=6 pass="); g_n(pass[0]) 81 if pass[0]==6 { g_w(" verdict=GREEN\n"); sys_exit(0); return 0 } 82 g_w(" verdict=RED\n"); sys_exit(1); return 1 83}