nx_sketch_ewma.nx source
↩ module page · 137 lines · 4334 B
1// sketch_ewma.nx -- exponentially-weighted moving average (EWMA).
2//
3// Single-pass time-series smoother:
4// x_new = alpha * sample + (1 - alpha) * x_old
5//
6// Smaller alpha = more smoothing (longer memory). alpha=1 means
7// "no smoothing" -- track current sample only. alpha near 0 means
8// "very long memory."
9//
10// PARAMETERIZATION:
11// alpha is expressed in parts-per-million (PPM). Valid range
12// [1, 1_000_000]. alpha_ppm=10000 = 0.01 = "Q1 weight of 1% per sample"
13// ~ effective window ~100 samples.
14//
15// INTEGER ARITHMETIC (no f64 in sibling):
16// x_new = (alpha_ppm * sample + (1e6 - alpha_ppm) * x_old) / 1e6
17//
18// OVERFLOW BUDGET:
19// |sample|, |x_old| < 2^32 to avoid overflow in alpha * sample.
20// For |sample| up to 2^43 (~8.8e12) safe given alpha_ppm <= 1e6 (2^20).
21//
22// USE CASES:
23// - SRE latency smoothing (oncall dashboards)
24// - financial price tracking (EMA in technical analysis)
25// - sensor smoothing (IoT temperature/humidity)
26//
27// LOSSLESS-LANGUAGE DISCIPLINE: EWMA's "approximation" is the
28// systematic bias toward recent samples -- a feature, not loss.
29// We declare envelope_kind = NX_ENV_ABS, param_a = quantization
30// error per step (<= 1). MaturityClass = Production (deterministic
31// recurrence, no probabilistic bounds).
32
33// nx_safety_envelope:
34// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
35// sil_target: SIL1
36// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
37// verdict: NOT_YET_EVALUATED
38
39import "nx_syscalls.nx"
40import "nx_sketch_types.nx"
41
42const NX_EWMA_ALPHA_MIN: i64 = 1
43const NX_EWMA_ALPHA_MAX: i64 = 1000000
44const NX_EWMA_SCALE: i64 = 1000000
45
46struct Ewma {
47 alpha_ppm: i64,
48 value: i64,
49 count: i64,
50 has_data: i64,
51}
52
53// === construction =================================================
54
55func nx_ewma_alloc(alpha_ppm: i64) -> *Ewma {
56 if alpha_ppm < NX_EWMA_ALPHA_MIN { return 0 as *Ewma }
57 if alpha_ppm > NX_EWMA_ALPHA_MAX { return 0 as *Ewma }
58 let raw: *u8 = sys_mmap(40)
59 let e: *Ewma = raw as *Ewma
60 e.alpha_ppm = alpha_ppm
61 e.value = 0
62 e.count = 0
63 e.has_data = 0
64 return e
65}
66
67// === overflow guard ==============================================
68//
69// Returns 1 iff alpha_ppm * sample + (1e6 - alpha_ppm) * value
70// would NOT overflow i64. Conservative bound: max(|sample|, |value|)
71// must satisfy max * 1e6 < 2^62. max < 2^42 ~ 4.4e12 safe.
72
73const NX_EWMA_SAFE_LIMIT: i64 = 4000000000000 // 4e12
74
75func nx_ewma_safe_p(sample: i64) -> i64 {
76 var s: i64 = sample
77 if s < 0 { s = -s }
78 if s >= NX_EWMA_SAFE_LIMIT { return 0 }
79 return 1
80}
81
82// === add ==========================================================
83//
84// First sample: initialize value directly (warm-up). Subsequent:
85// apply EWMA recurrence.
86
87func nx_ewma_add(e: *Ewma, sample: i64) -> i64 {
88 if nx_ewma_safe_p(sample) == 0 { return -1 }
89 if e.has_data == 0 {
90 e.value = sample
91 e.has_data = 1
92 e.count = 1
93 return 0
94 }
95 // EWMA recurrence:
96 // x_new = alpha * sample + (1 - alpha) * x_old
97 // In ppm:
98 // x_new = (alpha_ppm * sample + (1e6 - alpha_ppm) * x_old) / 1e6
99 let a: i64 = e.alpha_ppm
100 let b: i64 = NX_EWMA_SCALE - a
101 e.value = (a * sample + b * e.value) / NX_EWMA_SCALE
102 e.count = e.count + 1
103 return 0
104}
105
106// === queries ======================================================
107
108func nx_ewma_value(e: *Ewma) -> i64 {
109 return e.value
110}
111
112func nx_ewma_count(e: *Ewma) -> i64 {
113 return e.count
114}
115
116// Effective window: ~ 1 / alpha samples. In PPM: 1e6 / alpha_ppm.
117// E.g. alpha_ppm=10000 -> effective window 100.
118func nx_ewma_effective_window(e: *Ewma) -> i64 {
119 return NX_EWMA_SCALE / e.alpha_ppm
120}
121
122// === typed envelope ===============================================
123//
124// Quantization error per step <= 1 (truncation in i64 division).
125// Cumulative error bounded by O(log N) steps assuming i.i.d. noise.
126// We declare a conservative bound of 1 (worst case at each step).
127
128func nx_ewma_query(e: *Ewma) -> *ApproxI64 {
129 return nx_approx_new(e.value, NX_ENV_ABS, 1,
130 1000000000,
131 NX_MATURITY_PRODUCTION,
132 NX_ADV_HONEST)
133}
134
135func nx_ewma_memory_bytes(e: *Ewma) -> i64 {
136 return 40
137}