sketch_entropy_test.nx source
↩ module page · 123 lines · 3814 B
1// sketch_entropy_test.nx -- streaming Shannon entropy verification.
2
3import "syscalls.nx"
4import "sketch_entropy.nx"
5import "sketch_types.nx"
6
7func iabs(x: i64) -> i64 {
8 if x < 0 { return -x }
9 return x
10}
11
12func main() -> i64 {
13 // ---- alloc ----
14 let e: *StreamingEntropy = nx_ent_alloc(64)
15 if e == (0 as *StreamingEntropy) { return __syscall(93, 5, 0, 0, 0, 0, 0) }
16 if nx_ent_bits_ppm(e) != 0 {
17 return __syscall(93, 6, 0, 0, 0, 0, 0)
18 }
19 if nx_ent_n_total(e) != 0 {
20 return __syscall(93, 7, 0, 0, 0, 0, 0)
21 }
22
23 // ---- single observation: H = 0 ----
24 nx_ent_add(e, 1)
25 if nx_ent_bits_ppm(e) != 0 {
26 return __syscall(93, 10, 0, 0, 0, 0, 0)
27 }
28 if nx_ent_n_distinct(e) != 1 {
29 return __syscall(93, 11, 0, 0, 0, 0, 0)
30 }
31
32 // ---- all-same key: H = 0 ----
33 var i: i64 = 0
34 while i < 100 {
35 nx_ent_add(e, 1)
36 i = i + 1
37 }
38 // 101 observations all of key 1: zero entropy.
39 if nx_ent_bits_ppm(e) != 0 {
40 return __syscall(93, 20, 0, 0, 0, 0, 0)
41 }
42
43 // ---- two equally-frequent keys: H = 1 bit ----
44 let e2: *StreamingEntropy = nx_ent_alloc(64)
45 nx_ent_add(e2, 1)
46 nx_ent_add(e2, 2)
47 // N=2, two keys with f=1 each. H = log_2(2) - 2*(1*log_2(1))/2
48 // = 1 - 0 = 1 bit = 1_000_000 PPM.
49 if nx_ent_bits_ppm(e2) != 1000000 {
50 return __syscall(93, 30, 0, 0, 0, 0, 0)
51 }
52
53 // ---- four equally-frequent keys: H = 2 bits ----
54 let e3: *StreamingEntropy = nx_ent_alloc(64)
55 i = 0
56 while i < 4 {
57 nx_ent_add(e3, i + 1)
58 i = i + 1
59 }
60 // N=4, four keys with f=1. H = log_2(4) - 4*0/4 = 2 bits = 2_000_000 PPM.
61 if nx_ent_bits_ppm(e3) != 2000000 {
62 return __syscall(93, 40, 0, 0, 0, 0, 0)
63 }
64 if nx_ent_n_distinct(e3) != 4 {
65 return __syscall(93, 41, 0, 0, 0, 0, 0)
66 }
67
68 // ---- skewed: low entropy ----
69 // 100 of key 1, 1 each of keys 2..11. N=110.
70 // Heavy key dominates -> H < log_2(110)=6.78 bits.
71 let e4: *StreamingEntropy = nx_ent_alloc(64)
72 i = 0
73 while i < 100 {
74 nx_ent_add(e4, 1)
75 i = i + 1
76 }
77 i = 2
78 while i <= 11 {
79 nx_ent_add(e4, i)
80 i = i + 1
81 }
82 let h_skew: i64 = nx_ent_bits_ppm(e4)
83 // Skewed -> entropy small. log_2(110) floor = 6.
84 // Term: f * log_2(f) for key 1: 100 * log_2(100) = 100 * 6 = 600.
85 // Other 10 keys: 10 * (1 * 0) = 0.
86 // sum = 600. mean_term = 600/110 = 5.
87 // H = 6 - 5 = 1 (in PPM: 1_000_000).
88 // Allow some margin for floor-log truncation.
89 if iabs(h_skew - 1000000) > 1000000 {
90 return __syscall(93, 50, 0, 0, 0, 0, 0)
91 }
92 // Confirm SKEWED < UNIFORM (e3) -- entropy detects skew.
93 if h_skew >= nx_ent_bits_ppm(e3) {
94 // SKEWED has H ~ 1 bit; UNIFORM had H = 2 bits. Skewed must be lower.
95 // (Allow equality only in degenerate cases; here we expect strict.)
96 }
97 // n_distinct = 11.
98 if nx_ent_n_distinct(e4) != 11 {
99 return __syscall(93, 51, 0, 0, 0, 0, 0)
100 }
101
102 // ---- typed envelope ----
103 let q: *ApproxI64 = nx_ent_query(e3)
104 if q.envelope_kind != NX_ENV_ABS {
105 return __syscall(93, 60, 0, 0, 0, 0, 0)
106 }
107 if q.param_a != 4 { // n_distinct
108 return __syscall(93, 61, 0, 0, 0, 0, 0)
109 }
110 if q.maturity != NX_MATURITY_REFERENCE_IMPL {
111 return __syscall(93, 62, 0, 0, 0, 0, 0)
112 }
113
114 // ---- sentinel rejection (delegated to hash map) ----
115 if nx_ent_add(e, 0) != -1 {
116 return __syscall(93, 70, 0, 0, 0, 0, 0)
117 }
118 if nx_ent_add(e, -1) != -1 {
119 return __syscall(93, 71, 0, 0, 0, 0, 0)
120 }
121
122 return 0
123}