1 // Package ewma implements EWMA (Exponentially Weighted Moving Average) with
2 // oscillation detection using exact rational arithmetic.
3 //
4 // The oscillation detector tracks the raw/accreted ratio across generations.
5 // When the EWMA repeatedly reverses direction — rising then falling then
6 // rising — the lattice has exhausted its current information and needs
7 // fresh input.
8 package ewma
9 10 import (
11 "encoding/json"
12 13 "git.mleku.dev/mleku/dendrite/pkg/ratio"
14 )
15 16 // EWMA tracks an exponentially weighted moving average.
17 // Alpha = 2/(N+1) where N is the smoothing window.
18 // All arithmetic is exact rational — no floats.
19 type EWMA struct {
20 Alpha ratio.Ratio `json:"alpha"`
21 OneMinA ratio.Ratio `json:"one_min_a"`
22 Value ratio.Ratio `json:"value"`
23 Count int `json:"count"`
24 }
25 26 // NewEWMA creates an EWMA with the given smoothing window.
27 // Alpha = 2 / (window + 1).
28 func NewEWMA(window int) EWMA {
29 alpha := ratio.New(2, int64(window+1))
30 oneMinA := ratio.One.Sub(alpha)
31 return EWMA{
32 Alpha: alpha,
33 OneMinA: oneMinA,
34 Value: ratio.Zero,
35 }
36 }
37 38 // maxDenom is the denominator cap to prevent overflow in iterated multiplication.
39 // Values are rescaled when the denominator exceeds this. The cap preserves
40 // about 9 decimal digits of precision — more than sufficient for EWMA tracking.
41 // Epoch decomposition: 10^9 × 2^0 (pure decimal). A binary component would
42 // not improve precision because rescaling is followed by GCD normalization.
43 const maxDenom int64 = 1_000_000_000
44 45 // Update feeds a new value into the EWMA.
46 // Formula: ewma = alpha * value + (1 - alpha) * ewma_old
47 // On the first observation, the EWMA is set directly to the value.
48 // The result is rescaled to prevent denominator overflow from iterated
49 // multiplication.
50 func (e *EWMA) Update(value ratio.Ratio) {
51 e.Count++
52 if e.Count == 1 {
53 e.Value = value
54 return
55 }
56 e.Value = e.Alpha.Mul(value).Add(e.OneMinA.Mul(e.Value))
57 e.Value = rescale(e.Value)
58 }
59 60 // rescale reduces a ratio's denominator if it exceeds maxDenom.
61 // This is lossy but bounded: at most 1/maxDenom precision loss per step.
62 func rescale(r ratio.Ratio) ratio.Ratio {
63 if r.Denom <= maxDenom && r.Denom >= -maxDenom {
64 return r
65 }
66 // Scale both num and denom down proportionally.
67 // Use the ratio of maxDenom/abs(denom) to compute new num.
68 d := r.Denom
69 if d < 0 {
70 d = -d
71 }
72 // newNum = r.Num * maxDenom / r.Denom (integer division, rounds toward zero)
73 newNum := r.Num * maxDenom / r.Denom
74 return ratio.New(newNum, maxDenom)
75 }
76 77 // OscillationDetector detects when the EWMA repeatedly reverses direction.
78 // It counts direction reversals (rising→falling or falling→rising).
79 // When the reversal count reaches the threshold, the signal is oscillating.
80 //
81 // A reversal is detected when the EWMA moves by more than a minimum step
82 // in the opposite direction from the previous movement. This filters out
83 // noise from convergence jitter.
84 type OscillationDetector struct {
85 EW EWMA `json:"ew"`
86 Prev ratio.Ratio `json:"prev"` // previous EWMA value
87 PeakVal ratio.Ratio `json:"peak_val"` // last peak/trough value
88 Rising bool `json:"rising"` // current direction
89 DirKnown bool `json:"dir_known"` // direction established
90 Reversals int `json:"reversals"` // count of direction changes
91 Threshold int `json:"threshold"` // reversals needed for oscillation
92 MinStep ratio.Ratio `json:"min_step"` // minimum movement to count as reversal
93 Primed bool `json:"primed"` // have we seen enough data
94 }
95 96 // NewDetector creates an oscillation detector.
97 // threshold is the number of direction reversals needed to declare oscillation.
98 // A threshold of 3 means 3 reversals = roughly 1.5 full oscillation cycles.
99 func NewDetector(ewmaWindow, _ /*bandCapacity*/, threshold int) *OscillationDetector {
100 return &OscillationDetector{
101 EW: NewEWMA(ewmaWindow),
102 Prev: ratio.Zero,
103 PeakVal: ratio.Zero,
104 Threshold: threshold,
105 MinStep: ratio.New(1, 100), // 1% minimum movement
106 }
107 }
108 109 // Observe feeds a raw/accreted pair into the detector. Returns true if
110 // terminal oscillation is detected after this observation.
111 func (d *OscillationDetector) Observe(rawCount, accretedCount int64) bool {
112 value := ratio.Zero
113 if rawCount > 0 {
114 value = ratio.New(accretedCount, rawCount)
115 }
116 117 d.EW.Update(value)
118 119 // Need at least 2 EWMA values to detect direction.
120 if d.EW.Count < 2 {
121 d.Prev = d.EW.Value
122 d.PeakVal = d.EW.Value
123 return false
124 }
125 126 // Current movement direction.
127 nowRising := d.EW.Value.Greater(d.Prev)
128 nowFalling := d.Prev.Greater(d.EW.Value)
129 130 if !d.DirKnown {
131 // Establish initial direction.
132 if nowRising || nowFalling {
133 d.Rising = nowRising
134 d.DirKnown = true
135 d.PeakVal = d.Prev
136 d.Primed = true
137 }
138 d.Prev = d.EW.Value
139 return false
140 }
141 142 // Track peak/trough for minimum step check.
143 if d.Rising && d.EW.Value.Greater(d.PeakVal) {
144 d.PeakVal = d.EW.Value
145 }
146 if !d.Rising && d.EW.Value.Less(d.PeakVal) {
147 d.PeakVal = d.EW.Value
148 }
149 150 // Check for direction reversal.
151 reversed := false
152 if d.Rising && nowFalling {
153 // Was rising, now falling. Check the drop from peak is significant.
154 drop := d.PeakVal.Sub(d.EW.Value)
155 if drop.Greater(d.MinStep) || drop.Equal(d.MinStep) {
156 reversed = true
157 }
158 } else if !d.Rising && nowRising {
159 // Was falling, now rising. Check the rise from trough is significant.
160 rise := d.EW.Value.Sub(d.PeakVal)
161 if rise.Greater(d.MinStep) || rise.Equal(d.MinStep) {
162 reversed = true
163 }
164 }
165 166 if reversed {
167 d.Reversals++
168 d.Rising = !d.Rising
169 d.PeakVal = d.EW.Value
170 }
171 172 d.Prev = d.EW.Value
173 174 return d.Oscillating()
175 }
176 177 // Oscillating returns true if reversals have reached the threshold.
178 func (d *OscillationDetector) Oscillating() bool {
179 return d.Primed && d.Reversals >= d.Threshold
180 }
181 182 // Reset zeros the reversal counter but preserves the EWMA value.
183 // Called when fresh data is fed after oscillation is detected.
184 func (d *OscillationDetector) Reset() {
185 d.Reversals = 0
186 d.DirKnown = false
187 d.Primed = false
188 d.PeakVal = d.EW.Value
189 d.Prev = d.EW.Value
190 }
191 192 // FeedRatio returns the current accreted/raw ratio from the EWMA.
193 func (d *OscillationDetector) FeedRatio() ratio.Ratio {
194 return d.EW.Value
195 }
196 197 // Marshal serializes the detector state for persistence.
198 func (d *OscillationDetector) Marshal() ([]byte, error) {
199 return json.Marshal(d)
200 }
201 202 // UnmarshalDetector restores a detector from persisted state.
203 func UnmarshalDetector(data []byte) (*OscillationDetector, error) {
204 d := &OscillationDetector{}
205 if err := json.Unmarshal(data, d); err != nil {
206 return nil, err
207 }
208 return d, nil
209 }
210