5
$\begingroup$

Is it possible to implement a moving average in C without the need for a window of samples?

I've found that I can optimize a bit, by choosing a window size that's a power of two to allow for bit-shifting instead of dividing, but not needing a buffer would be nice. Is there a way to express a new moving average result only as a function of the old result and the new sample?

Define an example moving average, across a window of 4 samples to be:

ma <= (a + b + c + d) / 4

Add new sample e:

ma_new <= (a + b + c + d) / 4 - (a / 4) + (e / 4)
ma_new(ma, oldest_sample, new_sample) <= ma - (a / 4) + (e / 4)
$\endgroup$
8
$\begingroup$

A moving average can be implemented recursively, but for an exact computation of the moving average you have to remember the oldest input sample in the sum (i.e. the a in your example). For a length $N$ moving average you compute:

$$y[n]=\frac{1}{N}\sum_{k=n-N+1}^nx[k]\tag{1}$$

where $y[n]$ is the output signal and $x[n]$ is the input signal. Eq. (1) can be written recursively as

$$y[n]=y[n-1]+\frac{1}{N}(x[n]-x[n-N])\tag{2}$$

So you always need to remember the sample $x[n-N]$ in order to compute (2).

As pointed out by Conrad Turner, you can use an (infinitely long) exponential window instead, which allows you to compute the output only from the past output and the current input:

$$y[n]=\alpha x[n]+(1-\alpha)y[n-1]\tag{3}$$

but this is not a standard (unweighted) moving average but an exponentially weighted moving average, where samples further in the past get a smaller weight, but (at least in theory) you never forget anything (the weights just get smaller and smaller for samples far in the past).

$\endgroup$
  • $\begingroup$ Your first method is exactly that in tarabyte's original post, but they did not want to maintain a buffer and this does require a buffer of length N, holding the values in the current moving average. $\endgroup$ – Conrad Turner Feb 3 '15 at 15:52
  • 2
    $\begingroup$ @ConradTurner: That's right. I wanted to show that for any $N$ you always need the sample $x[n-N]$, otherwise you can't do the standard moving average, recursive or not. The exponential moving average could be an option, but it's a different thing. It all depends on what the OP wants. $\endgroup$ – Matt L. Feb 3 '15 at 16:03
6
$\begingroup$

What is wrong with a fading memory (exponential) moving average:

ma_new = alpha * new_sample + (1-alpha) * ma_old
$\endgroup$
  • 1
    $\begingroup$ Let me count the ways: 1) it's not a moving average (it's auto-regressive). 2) It's not finite (duration) impulse response. 3) It can never be linear phase (like an FIR can). On the plus side: 1) it's ludicrously simple, 2) It works in many practical applications, and 3) it meets the OP's requirement for no buffer. Plus one, by the way. :-) $\endgroup$ – Peter K. Feb 3 '15 at 19:03
  • $\begingroup$ Its not being a moving average really is a matter of terminology many references do describe it as such (not just Wikipedia). Terminology varies from application domain to application domain also. $\endgroup$ – Conrad Turner Feb 3 '15 at 19:29
  • 3
    $\begingroup$ @PeterK.: Well, it moves, and it computes a (weighted) average. So 'exponentially weighted moving average' does actually make sense (to me). $\endgroup$ – Matt L. Feb 3 '15 at 20:18
  • 1
    $\begingroup$ +2 to the number names I've seen allocated to that. I've heard it called a leaky-integrator, low-pass filter, FIR filter and now exponential moving average and fading memory moving average. $\endgroup$ – tarabyte Feb 3 '15 at 23:54
  • 1
    $\begingroup$ @tarabyte It's definitely not a FIR filter. It is a variety of IIR filter. $\endgroup$ – Kevin Reid Feb 4 '15 at 4:32
0
$\begingroup$

I implemented a moving average without individual item memory for a GPS tracking program I wrote.

I start with 1 sample and divide by 1 to get the current avg.

I then add anothe sample and divide by 2 to the the current avg.

This continues until I get to the length of the average.

Each time afterwards, I add in the new sample, get the average and remove that average from the total.

I am not a mathematician but this seemed like a good way to do it. I figured it would turn the stomach of a real math guy but, it turns out it is one of the accepted ways of doing it. And it works well. Just remember that the higher your "length" the slower it is following what you want to follow. That may not matter most of the time but when following satellites, if you are slow, the trail could be far from the actual position and it will look bad. You could have a gap between the sat and the trailing dots. I chose a length of 15 updated 6 times per minute to get adequate smoothing and not get too far from the actual sat position with the smoothed trail dots.

$\endgroup$
0
$\begingroup$

This method gives you an approximation of the moving average by basically assuming that the value of the sample window_size samples ago is equal to the previous moving average, which is updated every window_size samples.

It works well if your values are randomly distributed, but outliers will skew it more than the exact moving average.

previous_average = 0
total = 0
for count, sample in enumerate(samples):
    if count % window_size == 0: # Update previous_average every window_size samples
        previous_average = total/window_size
    total += sample
    if count > window_size:
        total -= previous_average
    current_average = total/window_size

With the 4 point example we can estimate the error:

$\begin{align} y_n = \frac{(a + b + c + d)}{4} &, y_{n+1} = \frac{(a+b+c+d)}{4} + \frac{e}{4} - \frac{a}{4} \\ y*_{n+1} &= \frac{(a + b + c + d) - y_{n} + e}{4} \\ &= \frac{(a+b+c+d)}{4} - \frac{(a+b+c+d)}{16} + \frac{e}{4} \\ &= \frac{3(a+b+c+d)}{16} + \frac{e}{4} \\ \end{align}$

$\begin{align} E &= y*_{n+1} - y_{n+1} \\ &= \frac{3a}{16} - \frac{a+b+c+d}{16} \end{align}$

I am lazily going to assume that with an arbitrary window size $W$

$\begin{align} E &= \frac{(W-1)a}{W^2} - \frac{y_n}{W} \\ \end{align}$

If $W$ is large enough, then:

$\begin{align} E &\approx \frac{a - y_n}{W} \end{align}$

Which is the residual of point $a$ divided by the total number of residuals...

This is just an approximation of the error for the first count % window_size == 0 iteration, and I'm already trying to go further than my maths abilities, but since we can start at any $x_n = a$ it suggests that as long as $W$ is sufficiently large or each $x_{n} - y_{n}$ is sufficiently small then this average will produce the same average residual as a fit with the exact formula.

I've attached an image from my test script showing the exact 100 point moving average compared to this method:

Comparison of exact moving average with this method

$\endgroup$
  • $\begingroup$ Please don't hate me if this method is garbage but I tested it with Python's random.random and it worked... $\endgroup$ – szmoore Jul 19 '18 at 8:20
  • $\begingroup$ Update: in my use case we did end up deciding this method was garbage $\endgroup$ – szmoore Aug 16 '18 at 2:36
  • $\begingroup$ Just out of curiosity, for what reasons did you end up deciding this method was garbage? $\endgroup$ – Slater Oct 23 '18 at 15:25
  • 1
    $\begingroup$ @Slater The overall error is not large and the signal has the correct shape, but the locations, number, and heights of the peaks in the signal are very different. $\endgroup$ – szmoore Feb 12 at 7:44
-2
$\begingroup$

initialize total = 0, count=0 (each time seeing a new value

  1)  total+=newValue
  2)  count++;
  3)  average = total/counter

Then one input (scanf), one add total+=newValue, one increment (count++), one divide average = (total/count)

This would be a moving average over all inputs

To calculate the average over only the last 4 inputs, would require 4 inputvariables, perhaps copying each input to an older inputvariable, then calculating the new moving average. as sum of the 4 inputvariables, divided by 4 (right shift 2 would be good if all the inputs were positive to make the average calculation

$\endgroup$
  • 2
    $\begingroup$ That will actually calculate the total average and NOT the moving average. As count gets larger the impact of any new input sample becomes vanishingly small $\endgroup$ – Hilmar Feb 3 '15 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.