code wiki / _hdl_build / nx_recip_div_w_test.nx
nx_recip_div_w_test.nx source
↩ module page · 133 lines · 4513 B
1// nx_recip_div_w_test.nx -- proves the WIDTH-PARAMETERIZED Goldschmidt generator
2// (nx_recip_div_w) across multiple widths: W=20, 28, 30. (W=24 is the heavy
3// anchor in nx_recip_div24_test, 2.3M vectors.) Each width is TRIANGULATED:
4// gate-net (LEG A) vs an independent restoring divider (LEG B) vs the i64 oracle
5// (LEG C), quotient AND remainder, over dense-small + random full-width + edges.
6// Known answer: "W20=0 W28=0 W30=0" (mismatch counts), exit 0 iff all zero.
7
8import "nx_recip_div_w.nx"
9
10const RDWT_LCG_A: i64 = 6364136223846793005
11const RDWT_LCG_C: i64 = 1442695040888963407
12
13func _emit_cstr(s: *u8) -> i64 { var n: i64 = 0; while s[n] != (0 as u8) { n = n + 1 } sys_write(1, s, n); return 0 }
14func _emit_dec(v: i64) -> i64 {
15 let b: *u8 = sys_mmap(28); var n: i64 = v; if n < 0 { n = 0 - n }
16 let t: *u8 = sys_mmap(28); var k: i64 = 0
17 if n == 0 { t[0] = 48; k = 1 }
18 while n > 0 { t[k] = 48 + (n % 10); n = n / 10; k = k + 1 }
19 var i: i64 = 0; while i < k { b[i] = t[k - 1 - i]; i = i + 1 }
20 sys_write(1, b, k); return 0
21}
22
23// LEG B: independent restoring divider over W bits.
24func rdwt_restoring(N: i64, D: i64, W: i64) -> i64 {
25 var q: i64 = 0
26 var r: i64 = 0
27 var i: i64 = W - 1
28 while i >= 0 {
29 r = (r << 1) | ((N >> i) & 1)
30 if r >= D { r = r - D; q = q | (1 << i) }
31 i = i - 1
32 }
33 return q
34}
35
36func rdwt_run(g: *NxGsim, qnet: i64, rnet: i64, N: i64, D: i64, r_out: *i64) -> i64 {
37 g.vals[0] = N
38 g.vals[1] = D
39 if nx_gsim_run(g) != NX_GSIM_OK { r_out[0] = 0 - 1; return 0 - 1 }
40 r_out[0] = g.vals[rnet]
41 return g.vals[qnet]
42}
43
44// Sweep one width; returns the mismatch count (0 = all three legs agree, q+r).
45func rdwt_sweep(W: i64, nrand: i64) -> i64 {
46 let vals: *i64 = sys_mmap(8 * 4096) as *i64
47 let cells: *NxGsimCell = sys_mmap(48 * 4096) as *NxGsimCell
48 let g: *NxGsim = sys_mmap(64) as *NxGsim
49 g.vals = vals; g.n_nets = 2; g.cells = cells; g.n_cells = 0
50 let rob: *i64 = sys_mmap(8) as *i64; rob[0] = 0
51 let qnet: i64 = nx_recip_div_w_synth(g, 0, 1, W, rob)
52 let rnet: i64 = rob[0]
53 let r_out: *i64 = sys_mmap(8) as *i64
54 let mask: i64 = (1 << W) - 1
55
56 var bad: i64 = 0
57
58 // dense: D in [1,32], N in [0,511]
59 var D: i64 = 1
60 while D <= 32 {
61 var N: i64 = 0
62 while N <= 511 {
63 let a: i64 = rdwt_run(g, qnet, rnet, N, D, r_out)
64 let ar: i64 = r_out[0]
65 let b: i64 = rdwt_restoring(N, D, W)
66 let c: i64 = N / D
67 let cr: i64 = N - (N / D) * D
68 if a != b { bad = bad + 1 }
69 if a != c { bad = bad + 1 }
70 if ar != cr { bad = bad + 1 }
71 N = N + 1
72 }
73 D = D + 1
74 }
75
76 // random full-width
77 var seed: i64 = 99173 + W
78 var nr: i64 = 0
79 while nr < nrand {
80 seed = seed * RDWT_LCG_A + RDWT_LCG_C; var N: i64 = seed & mask
81 seed = seed * RDWT_LCG_A + RDWT_LCG_C; var D: i64 = (seed & mask)
82 if D == 0 { D = 1 }
83 let a: i64 = rdwt_run(g, qnet, rnet, N, D, r_out)
84 let ar: i64 = r_out[0]
85 let b: i64 = rdwt_restoring(N, D, W)
86 let c: i64 = N / D
87 let cr: i64 = N - (N / D) * D
88 if a != b { bad = bad + 1 }
89 if a != c { bad = bad + 1 }
90 if ar != cr { bad = bad + 1 }
91 nr = nr + 1
92 }
93
94 // edges
95 let en: *i64 = sys_mmap(8 * 6) as *i64
96 let ed: *i64 = sys_mmap(8 * 6) as *i64
97 en[0]=mask; ed[0]=1
98 en[1]=mask; ed[1]=mask
99 en[2]=mask; ed[2]=2
100 en[3]=0; ed[3]=mask
101 en[4]=1; ed[4]=1
102 en[5]=mask; ed[5]=(1 << (W - 1))
103 var e: i64 = 0
104 while e < 6 {
105 let a: i64 = rdwt_run(g, qnet, rnet, en[e], ed[e], r_out)
106 let ar: i64 = r_out[0]
107 let b: i64 = rdwt_restoring(en[e], ed[e], W)
108 let c: i64 = en[e] / ed[e]
109 let cr: i64 = en[e] - (en[e] / ed[e]) * ed[e]
110 if a != b { bad = bad + 1 }
111 if a != c { bad = bad + 1 }
112 if ar != cr { bad = bad + 1 }
113 e = e + 1
114 }
115 return bad
116}
117
118func main() -> i64 {
119 let b20: i64 = rdwt_sweep(20, 30000)
120 let b28: i64 = rdwt_sweep(28, 30000)
121 let b30: i64 = rdwt_sweep(30, 30000)
122
123 _emit_cstr("W20=" as *u8); _emit_dec(b20)
124 _emit_cstr(" W28=" as *u8); _emit_dec(b28)
125 _emit_cstr(" W30=" as *u8); _emit_dec(b30)
126 _emit_cstr("\n" as *u8)
127
128 if b20 != 0 { sys_exit(1); return 1 }
129 if b28 != 0 { sys_exit(2); return 2 }
130 if b30 != 0 { sys_exit(3); return 3 }
131 sys_exit(0)
132 return 0
133}