`n`is often called the window size, because the algorithm can be thought of as an window that slides over the data points.

By using a recursive formulation of the algorithm, the number of operations required per sample is reduced to one addition, one subtraction and one division. Since the formulation is independent of the window size `n`, the runtime complexity is O(1), i.e. constant.

The recursive formula of the unweighted moving average is , where `avg` is the rolling average and `x` represents a data point. So, whenever the window slides to the right, one data point, the tail, drops out and one data point, the head, moves in.

### Implementation

An implementation of the simple moving average has to take the following into account

**Algorithm initialization**As long as the window is not fully populated with values, the recursive formula fails.**Storage**Access to the tail element is required, which depending on the implementation requires a storage of`n`elements.

My implementation uses the presented formula when the window is totally populated with values, and otherwise switches to the formula , which updates the mean by recalculating the sum of the previous elements. Note that this can lead to numerical instabilities because of floating point arithmetic.

As far as memory consumption is concerned, the implementation uses iterators to keep track of head and tail elements. This leads to an implementation with constant memory requirements independent of the window size. Here is the update procedure that slides the window to the right.

// _head and _next are enumerators of the data points collection // _count is the number of elements in the window (at max _n) // _running is the moving average initialized with zero. public void Shift() { if (!_head.MoveNext()) throw new InvalidOperationException("Cannot move to next element"); double next = _head.Current; if (_count < _n) { // Window not filled _count++; _running = (_running * (_count - 1) + next) / _count; } else { _tail.MoveNext(); double drop= (double)_tail.Current; _running = _running + (next - drop) / _n; } }

In .NET most of the collections invalidate their enumerators when the underlying collection is modified. The implementation, however, relies on valid enumerators. Especially in streaming based applications the underlying collection needs modified when a new element arrives. One way to deal with that is to create a simple circular fixed size collection of size `n+1` that never invalidates its iterators and alternately add an element and call `Shift`.

It’s really interesting article. Thanks for good information.

I wish I could figure out how to actually implement this, as the Test function is very confusing to me… Do I need to convert data to Array, then run

SMA sma = new SMA(20, [array]); for a 20 period SMA? How do I handle shift() function? Is it necessary to implement constructors ?? (sorry for confusion).

Craig,

No you don’t need to convert your data into an array as long as your data implements IEnumerable[1] and the enumerated type is double. As far as your private messaging is concerned you need to convert the DataRow to something that is enumerable of double values. Your approach works.

Shift, slides the window one position to the left. For a dataset of say 40 values and a 20 period SMA you have 21 positions the window fits in (40 – 20 + 1). Each time you call Shift() the window is moved to the left by one position and Average() returns the SMA for the current window position. That is, the unweighted average of all values inside the window.

Additionally my implementation allows to calculate the SMA even if the window is not fully filled at the beginning. So in essence

Hope this helps. Any further questions?

[1] http://msdn.microsoft.com/en-us/library/9eekhta0.aspx