sketch_holt.nx source

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 31import "syscalls.nx" 32import "sketch_types.nx" 33 34const NX_HOLT_PPM_MAX: i64 = 1000000 35const NX_HOLT_PPM_MIN: i64 = 1 36 37struct Holt { 38 alpha_ppm: i64, 39 beta_ppm: i64, 40 level: i64, 41 trend: i64, 42 count: i64, 43 has_data: i64, 44} 45 46// === construction ================================================= 47 48func nx_holt_alloc(alpha_ppm: i64, beta_ppm: i64) -> *Holt { 49 if alpha_ppm < NX_HOLT_PPM_MIN { return 0 as *Holt } 50 if alpha_ppm > NX_HOLT_PPM_MAX { return 0 as *Holt } 51 if beta_ppm < NX_HOLT_PPM_MIN { return 0 as *Holt } 52 if beta_ppm > NX_HOLT_PPM_MAX { return 0 as *Holt } 53 let raw: *u8 = sys_mmap(48) 54 let h: *Holt = raw as *Holt 55 h.alpha_ppm = alpha_ppm 56 h.beta_ppm = beta_ppm 57 h.level = 0 58 h.trend = 0 59 h.count = 0 60 h.has_data = 0 61 return h 62} 63 64// === add ========================================================== 65// 66// First sample: initialize level to y, trend to 0. 67// Second sample: trend = y - level_prev; level updated normally. 68// Subsequent: full Holt recurrence. 69 70func nx_holt_add(h: *Holt, y: i64) -> i64 { 71 if h.has_data == 0 { 72 h.level = y 73 h.trend = 0 74 h.count = 1 75 h.has_data = 1 76 return 0 77 } 78 let prev_level: i64 = h.level 79 let alpha: i64 = h.alpha_ppm 80 let one_minus_alpha: i64 = NX_HOLT_PPM_MAX - alpha 81 let beta: i64 = h.beta_ppm 82 let one_minus_beta: i64 = NX_HOLT_PPM_MAX - beta 83 84 // level_t = alpha * y + (1-alpha) * (level_{t-1} + trend_{t-1}) 85 let level_carry: i64 = prev_level + h.trend 86 let new_level: i64 = (alpha * y + one_minus_alpha * level_carry) / NX_HOLT_PPM_MAX 87 88 // trend_t = beta * (level_t - level_{t-1}) + (1-beta) * trend_{t-1} 89 let level_delta: i64 = new_level - prev_level 90 let new_trend: i64 = (beta * level_delta + one_minus_beta * h.trend) / NX_HOLT_PPM_MAX 91 92 h.level = new_level 93 h.trend = new_trend 94 h.count = h.count + 1 95 return 0 96} 97 98// === queries ====================================================== 99 100func nx_holt_level(h: *Holt) -> i64 { 101 return h.level 102} 103 104func nx_holt_trend(h: *Holt) -> i64 { 105 return h.trend 106} 107 108// Forecast h steps ahead. 109func nx_holt_forecast(holt: *Holt, h: i64) -> i64 { 110 return holt.level + h * holt.trend 111} 112 113func nx_holt_count(h: *Holt) -> i64 { 114 return h.count 115} 116 117// === typed envelope =============================================== 118// 119// Forecasts inherit cumulative quantization error from each recurrence 120// step. We declare param_a = h (forecast horizon -- error grows 121// linearly with steps ahead). 122 123func nx_holt_query_forecast(holt: *Holt, h: i64) -> *ApproxI64 { 124 let v: i64 = nx_holt_forecast(holt, h) 125 return nx_approx_new(v, NX_ENV_ABS, h, 126 1000000000, 127 NX_MATURITY_PRODUCTION, 128 NX_ADV_HONEST) 129} 130 131func nx_holt_memory_bytes(h: *Holt) -> i64 { 132 return 48 133}