sketch_cusum.nx source

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 34import "syscalls.nx" 35import "sketch_types.nx" 36 37// Alarm verdict sealed values. 38const NX_CUSUM_NORMAL: i64 = 0 39const NX_CUSUM_SHIFT_UP: i64 = 1 40const NX_CUSUM_SHIFT_DOWN: i64 = 2 41 42struct Cusum { 43 k: i64, // reference target value 44 delta: i64, // slack tolerance (sub-threshold drift ignored) 45 h: i64, // alarm threshold 46 s_pos: i64, // cumulative upward shift 47 s_neg: i64, // cumulative downward shift 48 n: i64, // observation count 49 n_alarms: i64, // total alarms fired 50 last_verdict: i64, // last query verdict 51} 52 53// === construction ================================================= 54 55func nx_cusum_alloc(k: i64, delta: i64, h: i64) -> *Cusum { 56 if delta < 0 { return 0 as *Cusum } 57 if h <= 0 { return 0 as *Cusum } 58 let raw: *u8 = sys_mmap(72) 59 let c: *Cusum = raw as *Cusum 60 c.k = k 61 c.delta = delta 62 c.h = h 63 c.s_pos = 0 64 c.s_neg = 0 65 c.n = 0 66 c.n_alarms = 0 67 c.last_verdict = NX_CUSUM_NORMAL 68 return c 69} 70 71// === add ========================================================== 72 73func nx_cusum_add(c: *Cusum, x: i64) -> i64 { 74 let dev: i64 = x - c.k 75 let upper_excess: i64 = dev - c.delta 76 let lower_excess: i64 = -dev - c.delta 77 // S+ = max(0, S+ + upper_excess) 78 var new_pos: i64 = c.s_pos + upper_excess 79 if new_pos < 0 { new_pos = 0 } 80 c.s_pos = new_pos 81 // S- = max(0, S- + lower_excess) 82 var new_neg: i64 = c.s_neg + lower_excess 83 if new_neg < 0 { new_neg = 0 } 84 c.s_neg = new_neg 85 c.n = c.n + 1 86 return 0 87} 88 89// === verdict ====================================================== 90 91func nx_cusum_verdict(c: *Cusum) -> i64 { 92 if c.s_pos > c.h { return NX_CUSUM_SHIFT_UP } 93 if c.s_neg > c.h { return NX_CUSUM_SHIFT_DOWN } 94 return NX_CUSUM_NORMAL 95} 96 97// Query verdict and reset statistic on alarm. This is the typical 98// usage pattern: detect, alarm, reset, continue monitoring. 99func nx_cusum_step(c: *Cusum) -> i64 { 100 let v: i64 = nx_cusum_verdict(c) 101 c.last_verdict = v 102 if v != NX_CUSUM_NORMAL { 103 c.n_alarms = c.n_alarms + 1 104 c.s_pos = 0 105 c.s_neg = 0 106 } 107 return v 108} 109 110// === introspection ================================================ 111 112func nx_cusum_s_pos(c: *Cusum) -> i64 { return c.s_pos } 113func nx_cusum_s_neg(c: *Cusum) -> i64 { return c.s_neg } 114func nx_cusum_n(c: *Cusum) -> i64 { return c.n } 115func nx_cusum_n_alarms(c: *Cusum) -> i64 { return c.n_alarms } 116 117func nx_cusum_query(c: *Cusum) -> *ApproxI64 { 118 let v: i64 = nx_cusum_verdict(c) 119 return nx_approx_new(v, NX_ENV_ABS, 0, 1000000000, 120 NX_MATURITY_PRODUCTION, 121 NX_ADV_HONEST) 122} 123 124func nx_cusum_memory_bytes(c: *Cusum) -> i64 { 125 return 72 126} 127 128func nx_cusum_reset(c: *Cusum) -> i64 { 129 c.s_pos = 0 130 c.s_neg = 0 131 c.last_verdict = NX_CUSUM_NORMAL 132 return 0 133}