sketch_markov_vs_uniform_bench.nx source
↩ module page · 91 lines · 2890 B
1// sketch_markov_vs_uniform_bench.nx -- transition prediction bench.
2//
3// CLAIM: Markov chain learns state transition probabilities; predicts
4// next-state better than uniform random when transitions have structure.
5//
6// WORKLOAD: 4-state chain. Transitions strongly biased:
7// 0 -> 1 (80%) / 0 -> 2 (20%)
8// 1 -> 2 (80%) / 1 -> 3 (20%)
9// 2 -> 3 (80%) / 2 -> 0 (20%)
10// 3 -> 0 (80%) / 3 -> 1 (20%)
11// Train 1000 steps, then test 200 transitions.
12
13import "syscalls.nx"
14import "sketch_markov.nx"
15import "sketch_comparator.nx"
16import "sketch_types.nx"
17
18const NX_MKB_LCG_A: i64 = 1103515245
19const NX_MKB_LCG_C: i64 = 12345
20const NX_MKB_LCG_MOD: i64 = 0x7FFFFFFF
21
22func next_state(cur: i64, sim_ptr: *i64) -> i64 {
23 sim_ptr[0] = ((sim_ptr[0] * NX_MKB_LCG_A) + NX_MKB_LCG_C) & NX_MKB_LCG_MOD
24 let u: i64 = sim_ptr[0] & 0x3FF // 0..1023
25 let majority: i64 = 819 // 80%
26 if cur == 0 {
27 if u < majority { return 1 }
28 return 2
29 }
30 if cur == 1 {
31 if u < majority { return 2 }
32 return 3
33 }
34 if cur == 2 {
35 if u < majority { return 3 }
36 return 0
37 }
38 if u < majority { return 0 }
39 return 1
40}
41
42func main() -> i64 {
43 let mk: *Markov = nx_markov_alloc(4)
44 if mk == (0 as *Markov) { return __syscall(93, 1, 0, 0, 0, 0, 0) }
45
46 let sim_raw: *u8 = sys_mmap(8)
47 let sim: *i64 = sim_raw as *i64
48 sim[0] = 11
49
50 // ---- Train: 1000 transitions ----
51 var state: i64 = 0
52 var t: i64 = 0
53 while t < 1000 {
54 let nxt: i64 = next_state(state, sim)
55 nx_markov_observe(mk, state, nxt)
56 state = nxt
57 t = t + 1
58 }
59
60 // ---- Test: 200 predictions ----
61 var mk_correct: i64 = 0
62 var uniform_correct: i64 = 0
63 state = 0
64 t = 0
65 while t < 200 {
66 let actual_next: i64 = next_state(state, sim)
67 let mk_pred: i64 = nx_markov_predict(mk, state)
68 if mk_pred == actual_next { mk_correct = mk_correct + 1 }
69 // Uniform random predicts among 4 states; expected accuracy ~ 25%.
70 // Use deterministic pseudo-random for uniform.
71 sim[0] = ((sim[0] * NX_MKB_LCG_A) + NX_MKB_LCG_C) & NX_MKB_LCG_MOD
72 let uniform_pred: i64 = sim[0] & 3
73 if uniform_pred == actual_next { uniform_correct = uniform_correct + 1 }
74 state = actual_next
75 t = t + 1
76 }
77
78 // ---- Markov should be massively better (>=60% vs ~25%) ----
79 if mk_correct < 120 { return __syscall(93, 10, 0, 0, 0, 0, 0) }
80 if uniform_correct > 80 { return __syscall(93, 11, 0, 0, 0, 0, 0) } // sanity
81
82 let acc: *ComparisonResult = nx_cmp_accuracy(mk_correct, uniform_correct, 200, 50000)
83 if acc.verdict != NX_CMP_VERDICT_BEATS {
84 return __syscall(93, 20, 0, 0, 0, 0, 0)
85 }
86 if acc.delta_ppm < 100000 {
87 return __syscall(93, 21, 0, 0, 0, 0, 0)
88 }
89
90 return 0
91}