sketch_ewma.nx source
↩ module page · 131 lines · 4208 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
33import "syscalls.nx"
34import "sketch_types.nx"
35
36const NX_EWMA_ALPHA_MIN: i64 = 1
37const NX_EWMA_ALPHA_MAX: i64 = 1000000
38const NX_EWMA_SCALE: i64 = 1000000
39
40struct Ewma {
41 alpha_ppm: i64,
42 value: i64,
43 count: i64,
44 has_data: i64,
45}
46
47// === construction =================================================
48
49func nx_ewma_alloc(alpha_ppm: i64) -> *Ewma {
50 if alpha_ppm < NX_EWMA_ALPHA_MIN { return 0 as *Ewma }
51 if alpha_ppm > NX_EWMA_ALPHA_MAX { return 0 as *Ewma }
52 let raw: *u8 = sys_mmap(40)
53 let e: *Ewma = raw as *Ewma
54 e.alpha_ppm = alpha_ppm
55 e.value = 0
56 e.count = 0
57 e.has_data = 0
58 return e
59}
60
61// === overflow guard ==============================================
62//
63// Returns 1 iff alpha_ppm * sample + (1e6 - alpha_ppm) * value
64// would NOT overflow i64. Conservative bound: max(|sample|, |value|)
65// must satisfy max * 1e6 < 2^62. max < 2^42 ~ 4.4e12 safe.
66
67const NX_EWMA_SAFE_LIMIT: i64 = 4000000000000 // 4e12
68
69func nx_ewma_safe_p(sample: i64) -> i64 {
70 var s: i64 = sample
71 if s < 0 { s = -s }
72 if s >= NX_EWMA_SAFE_LIMIT { return 0 }
73 return 1
74}
75
76// === add ==========================================================
77//
78// First sample: initialize value directly (warm-up). Subsequent:
79// apply EWMA recurrence.
80
81func nx_ewma_add(e: *Ewma, sample: i64) -> i64 {
82 if nx_ewma_safe_p(sample) == 0 { return -1 }
83 if e.has_data == 0 {
84 e.value = sample
85 e.has_data = 1
86 e.count = 1
87 return 0
88 }
89 // EWMA recurrence:
90 // x_new = alpha * sample + (1 - alpha) * x_old
91 // In ppm:
92 // x_new = (alpha_ppm * sample + (1e6 - alpha_ppm) * x_old) / 1e6
93 let a: i64 = e.alpha_ppm
94 let b: i64 = NX_EWMA_SCALE - a
95 e.value = (a * sample + b * e.value) / NX_EWMA_SCALE
96 e.count = e.count + 1
97 return 0
98}
99
100// === queries ======================================================
101
102func nx_ewma_value(e: *Ewma) -> i64 {
103 return e.value
104}
105
106func nx_ewma_count(e: *Ewma) -> i64 {
107 return e.count
108}
109
110// Effective window: ~ 1 / alpha samples. In PPM: 1e6 / alpha_ppm.
111// E.g. alpha_ppm=10000 -> effective window 100.
112func nx_ewma_effective_window(e: *Ewma) -> i64 {
113 return NX_EWMA_SCALE / e.alpha_ppm
114}
115
116// === typed envelope ===============================================
117//
118// Quantization error per step <= 1 (truncation in i64 division).
119// Cumulative error bounded by O(log N) steps assuming i.i.d. noise.
120// We declare a conservative bound of 1 (worst case at each step).
121
122func nx_ewma_query(e: *Ewma) -> *ApproxI64 {
123 return nx_approx_new(e.value, NX_ENV_ABS, 1,
124 1000000000,
125 NX_MATURITY_PRODUCTION,
126 NX_ADV_HONEST)
127}
128
129func nx_ewma_memory_bytes(e: *Ewma) -> i64 {
130 return 40
131}