nx_sketch_cusum.nx source
↩ module page · 139 lines · 4320 B
1// sketch_cusum.nx -- CUSUM change-point detector (Page 1954).
2//
3// Detects shifts in stream mean from a known reference value. Maintains
4// two cumulative sums:
5//
6// S+_t = max(0, S+_{t-1} + (x_t - k - delta))
7// S-_t = max(0, S-_{t-1} - (x_t - k - delta))
8//
9// where:
10// k = reference target value (expected mean)
11// delta = slack tolerance (don't alarm on tiny perturbations)
12//
13// ALARM:
14// S+ > h -> upward shift detected (mean increased)
15// S- > h -> downward shift detected (mean decreased)
16// h is the alarm threshold (caller-tuned for false-positive rate).
17//
18// CAPABILITY:
19// - Real-time change-point detection in O(1) state
20// - SRE: latency / error-rate shift detection
21// - manufacturing QC: process drift
22// - finance: regime change
23// - sensor: equipment fault
24//
25// THEORETICAL:
26// Average run length (ARL) under null: ~ exp(h)
27// ARL under shift of size delta: ~ h / delta
28//
29// All integer arithmetic, EXACT semantics. Production tier.
30//
31// LOSSLESS-LANGUAGE DISCIPLINE: alarm verdict is exact (sealed enum-like).
32// nx_cusum_query returns the current statistic with NX_ENV_ABS, param_a = 0.
33
34// nx_safety_envelope:
35// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
36// sil_target: SIL1
37// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
38// verdict: NOT_YET_EVALUATED
39
40import "nx_syscalls.nx"
41import "nx_sketch_types.nx"
42
43// Alarm verdict sealed values.
44const NX_CUSUM_NORMAL: i64 = 0
45const NX_CUSUM_SHIFT_UP: i64 = 1
46const NX_CUSUM_SHIFT_DOWN: i64 = 2
47
48struct Cusum {
49 k: i64, // reference target value
50 delta: i64, // slack tolerance (sub-threshold drift ignored)
51 h: i64, // alarm threshold
52 s_pos: i64, // cumulative upward shift
53 s_neg: i64, // cumulative downward shift
54 n: i64, // observation count
55 n_alarms: i64, // total alarms fired
56 last_verdict: i64, // last query verdict
57}
58
59// === construction =================================================
60
61func nx_cusum_alloc(k: i64, delta: i64, h: i64) -> *Cusum {
62 if delta < 0 { return 0 as *Cusum }
63 if h <= 0 { return 0 as *Cusum }
64 let raw: *u8 = sys_mmap(72)
65 let c: *Cusum = raw as *Cusum
66 c.k = k
67 c.delta = delta
68 c.h = h
69 c.s_pos = 0
70 c.s_neg = 0
71 c.n = 0
72 c.n_alarms = 0
73 c.last_verdict = NX_CUSUM_NORMAL
74 return c
75}
76
77// === add ==========================================================
78
79func nx_cusum_add(c: *Cusum, x: i64) -> i64 {
80 let dev: i64 = x - c.k
81 let upper_excess: i64 = dev - c.delta
82 let lower_excess: i64 = -dev - c.delta
83 // S+ = max(0, S+ + upper_excess)
84 var new_pos: i64 = c.s_pos + upper_excess
85 if new_pos < 0 { new_pos = 0 }
86 c.s_pos = new_pos
87 // S- = max(0, S- + lower_excess)
88 var new_neg: i64 = c.s_neg + lower_excess
89 if new_neg < 0 { new_neg = 0 }
90 c.s_neg = new_neg
91 c.n = c.n + 1
92 return 0
93}
94
95// === verdict ======================================================
96
97func nx_cusum_verdict(c: *Cusum) -> i64 {
98 if c.s_pos > c.h { return NX_CUSUM_SHIFT_UP }
99 if c.s_neg > c.h { return NX_CUSUM_SHIFT_DOWN }
100 return NX_CUSUM_NORMAL
101}
102
103// Query verdict and reset statistic on alarm. This is the typical
104// usage pattern: detect, alarm, reset, continue monitoring.
105func nx_cusum_step(c: *Cusum) -> i64 {
106 let v: i64 = nx_cusum_verdict(c)
107 c.last_verdict = v
108 if v != NX_CUSUM_NORMAL {
109 c.n_alarms = c.n_alarms + 1
110 c.s_pos = 0
111 c.s_neg = 0
112 }
113 return v
114}
115
116// === introspection ================================================
117
118func nx_cusum_s_pos(c: *Cusum) -> i64 { return c.s_pos }
119func nx_cusum_s_neg(c: *Cusum) -> i64 { return c.s_neg }
120func nx_cusum_n(c: *Cusum) -> i64 { return c.n }
121func nx_cusum_n_alarms(c: *Cusum) -> i64 { return c.n_alarms }
122
123func nx_cusum_query(c: *Cusum) -> *ApproxI64 {
124 let v: i64 = nx_cusum_verdict(c)
125 return nx_approx_new(v, NX_ENV_ABS, 0, 1000000000,
126 NX_MATURITY_PRODUCTION,
127 NX_ADV_HONEST)
128}
129
130func nx_cusum_memory_bytes(c: *Cusum) -> i64 {
131 return 72
132}
133
134func nx_cusum_reset(c: *Cusum) -> i64 {
135 c.s_pos = 0
136 c.s_neg = 0
137 c.last_verdict = NX_CUSUM_NORMAL
138 return 0
139}