nx_sketch_holt.nx source
↩ module page · 139 lines · 4313 B
1// sketch_holt.nx -- Holt's linear method (double exponential smoothing).
2//
3// Time-series forecasting primitive that extends EWMA with a TREND
4// component. Two recurrences:
5//
6// level_t = alpha * y_t + (1 - alpha) * (level_{t-1} + trend_{t-1})
7// trend_t = beta * (level_t - level_{t-1}) + (1 - beta) * trend_{t-1}
8//
9// forecast(h) = level_t + h * trend_t (h steps ahead)
10//
11// alpha controls level smoothing; beta controls trend smoothing.
12// Both in PPM [1, 1_000_000].
13//
14// COMPLEMENTS EWMA (single-component):
15// - EWMA: smoothed level only; bad for trending data
16// - Holt: level + trend; tracks linear trajectories
17// - (Holt-Winters with seasonality is the natural v2)
18//
19// USE CASES:
20// - revenue / user-count forecasting
21// - SRE: capacity planning given growth trends
22// - sensor calibration drift detection
23//
24// INTEGER FIXED-POINT IMPLEMENTATION (no f64):
25// level, trend stored as i64. Updates via PPM arithmetic.
26// Overflow budget: |y| < 2^32 to keep alpha * y in i64.
27//
28// LOSSLESS-LANGUAGE DISCIPLINE: Production tier; envelope NX_ENV_ABS
29// with param_a = 1 (quantization error per step) and conf 1e9.
30
31// nx_safety_envelope:
32// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
33// sil_target: SIL1
34// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
35// verdict: NOT_YET_EVALUATED
36
37import "nx_syscalls.nx"
38import "nx_sketch_types.nx"
39
40const NX_HOLT_PPM_MAX: i64 = 1000000
41const NX_HOLT_PPM_MIN: i64 = 1
42
43struct Holt {
44 alpha_ppm: i64,
45 beta_ppm: i64,
46 level: i64,
47 trend: i64,
48 count: i64,
49 has_data: i64,
50}
51
52// === construction =================================================
53
54func nx_holt_alloc(alpha_ppm: i64, beta_ppm: i64) -> *Holt {
55 if alpha_ppm < NX_HOLT_PPM_MIN { return 0 as *Holt }
56 if alpha_ppm > NX_HOLT_PPM_MAX { return 0 as *Holt }
57 if beta_ppm < NX_HOLT_PPM_MIN { return 0 as *Holt }
58 if beta_ppm > NX_HOLT_PPM_MAX { return 0 as *Holt }
59 let raw: *u8 = sys_mmap(48)
60 let h: *Holt = raw as *Holt
61 h.alpha_ppm = alpha_ppm
62 h.beta_ppm = beta_ppm
63 h.level = 0
64 h.trend = 0
65 h.count = 0
66 h.has_data = 0
67 return h
68}
69
70// === add ==========================================================
71//
72// First sample: initialize level to y, trend to 0.
73// Second sample: trend = y - level_prev; level updated normally.
74// Subsequent: full Holt recurrence.
75
76func nx_holt_add(h: *Holt, y: i64) -> i64 {
77 if h.has_data == 0 {
78 h.level = y
79 h.trend = 0
80 h.count = 1
81 h.has_data = 1
82 return 0
83 }
84 let prev_level: i64 = h.level
85 let alpha: i64 = h.alpha_ppm
86 let one_minus_alpha: i64 = NX_HOLT_PPM_MAX - alpha
87 let beta: i64 = h.beta_ppm
88 let one_minus_beta: i64 = NX_HOLT_PPM_MAX - beta
89
90 // level_t = alpha * y + (1-alpha) * (level_{t-1} + trend_{t-1})
91 let level_carry: i64 = prev_level + h.trend
92 let new_level: i64 = (alpha * y + one_minus_alpha * level_carry) / NX_HOLT_PPM_MAX
93
94 // trend_t = beta * (level_t - level_{t-1}) + (1-beta) * trend_{t-1}
95 let level_delta: i64 = new_level - prev_level
96 let new_trend: i64 = (beta * level_delta + one_minus_beta * h.trend) / NX_HOLT_PPM_MAX
97
98 h.level = new_level
99 h.trend = new_trend
100 h.count = h.count + 1
101 return 0
102}
103
104// === queries ======================================================
105
106func nx_holt_level(h: *Holt) -> i64 {
107 return h.level
108}
109
110func nx_holt_trend(h: *Holt) -> i64 {
111 return h.trend
112}
113
114// Forecast h steps ahead.
115func nx_holt_forecast(holt: *Holt, h: i64) -> i64 {
116 return holt.level + h * holt.trend
117}
118
119func nx_holt_count(h: *Holt) -> i64 {
120 return h.count
121}
122
123// === typed envelope ===============================================
124//
125// Forecasts inherit cumulative quantization error from each recurrence
126// step. We declare param_a = h (forecast horizon -- error grows
127// linearly with steps ahead).
128
129func nx_holt_query_forecast(holt: *Holt, h: i64) -> *ApproxI64 {
130 let v: i64 = nx_holt_forecast(holt, h)
131 return nx_approx_new(v, NX_ENV_ABS, h,
132 1000000000,
133 NX_MATURITY_PRODUCTION,
134 NX_ADV_HONEST)
135}
136
137func nx_holt_memory_bytes(h: *Holt) -> i64 {
138 return 48
139}