sketch_ams_test.nx source
↩ module page · 110 lines · 3431 B
1// sketch_ams_test.nx -- AMS F_2 estimator verification.
2
3import "syscalls.nx"
4import "sketch_ams.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 + bounds rejection ----
14 let a: *AMS = nx_ams_alloc(5, 64, 42)
15 if a == (0 as *AMS) { return __syscall(93, 5, 0, 0, 0, 0, 0) }
16 if nx_ams_alloc(2, 64, 1) != (0 as *AMS) {
17 return __syscall(93, 6, 0, 0, 0, 0, 0)
18 }
19 if nx_ams_alloc(5, 2, 1) != (0 as *AMS) {
20 return __syscall(93, 7, 0, 0, 0, 0, 0)
21 }
22
23 // ---- empty: F_2 = 0 ----
24 if nx_ams_f2(a) != 0 {
25 return __syscall(93, 10, 0, 0, 0, 0, 0)
26 }
27
28 // ---- uniform distribution: F_2 small ----
29 // Insert 100 distinct items each with count 1. F_2 = 100 * 1² = 100.
30 var i: i64 = 1
31 while i <= 100 {
32 nx_ams_add(a, i, 1)
33 i = i + 1
34 }
35 let f2_uniform: i64 = nx_ams_f2(a)
36 // True F_2 = 100; allow within +/-30% via stderr 1/sqrt(64)=12.5%.
37 if iabs(f2_uniform - 100) > 30 {
38 return __syscall(93, 20, 0, 0, 0, 0, 0)
39 }
40
41 // ---- skewed distribution: F_2 huge ----
42 // One item with frequency 1000 + 1000 items with frequency 1.
43 // F_2 = 1000² + 1000 * 1² = 1_000_000 + 1000 = 1_001_000.
44 let a2: *AMS = nx_ams_alloc(7, 128, 7)
45 nx_ams_add(a2, 42, 1000) // heavy
46 i = 1
47 while i <= 1000 {
48 nx_ams_add(a2, i + 100, 1)
49 i = i + 1
50 }
51 let f2_skewed: i64 = nx_ams_f2(a2)
52 // True F_2 = 1_001_000; allow +/-15% (s=128 -> stderr 8.8%, median boost).
53 if iabs(f2_skewed - 1001000) > 200000 {
54 return __syscall(93, 30, 0, 0, 0, 0, 0)
55 }
56
57 // ---- single-item stream: F_2 = count² ----
58 let a3: *AMS = nx_ams_alloc(5, 64, 1)
59 nx_ams_add(a3, 7, 500)
60 let f2_single: i64 = nx_ams_f2(a3)
61 // True = 250_000. Tight bound for single-item.
62 if iabs(f2_single - 250000) > 25000 {
63 return __syscall(93, 40, 0, 0, 0, 0, 0)
64 }
65
66 // ---- typed envelope ----
67 let q: *ApproxI64 = nx_ams_query_f2(a2)
68 if q.envelope_kind != NX_ENV_REL_STDDEV {
69 return __syscall(93, 50, 0, 0, 0, 0, 0)
70 }
71 // s=128 -> stderr_ppb = 1e9 / sqrt(128) ~ 88M; isqrt(128)=11 -> 90M.
72 let isq: i64 = nx_ams_isqrt(128)
73 let expected_se: i64 = 1000000000 / isq
74 if iabs(q.param_a - expected_se) > 10000000 {
75 return __syscall(93, 51, 0, 0, 0, 0, 0)
76 }
77 if q.maturity != NX_MATURITY_REFERENCE_IMPL {
78 return __syscall(93, 52, 0, 0, 0, 0, 0)
79 }
80
81 // ---- merge ----
82 let m_a: *AMS = nx_ams_alloc(5, 64, 99)
83 let m_b: *AMS = nx_ams_alloc(5, 64, 99)
84 i = 1
85 while i <= 50 {
86 nx_ams_add(m_a, i, 1)
87 i = i + 1
88 }
89 i = 51
90 while i <= 100 {
91 nx_ams_add(m_b, i, 1)
92 i = i + 1
93 }
94 let merged: *AMS = nx_ams_merge(m_a, m_b)
95 if merged == (0 as *AMS) {
96 return __syscall(93, 60, 0, 0, 0, 0, 0)
97 }
98 // True F_2 of union (1..100 each count 1) = 100.
99 let f2_merged: i64 = nx_ams_f2(merged)
100 if iabs(f2_merged - 100) > 40 {
101 return __syscall(93, 61, 0, 0, 0, 0, 0)
102 }
103 // Mismatched seed -> NULL.
104 let m_c: *AMS = nx_ams_alloc(5, 64, 88)
105 if nx_ams_merge(m_a, m_c) != (0 as *AMS) {
106 return __syscall(93, 62, 0, 0, 0, 0, 0)
107 }
108
109 return 0
110}