Efficient algorithm/data structure to calculate moving averages Currently I am developing a graphic LCD system to display temperatures, flows, voltages, power and energy in a heat pump system. The use of a graphic LCD means that half of my SRAM and ~75% of my flash have been used up by a screen buffer and strings.

I am currently displaying min/max/average figures for energy At midnight when the daily figure resets, the system checks if the consumption for the day is above or below the previous minimum or maximum, and stores the value. The average is calculated by dividing the cumulative energy consumption by the number of days.

I would like to display the daily average over the last week and month (4 weeks for simplicity) i.e. a rolling average. Currently this involves maintaining an array of values for the last 28 days and calculating an average over the whole array for monthly and last 7 days for weekly.

Initially I was doing this using an array of floats (as the energy is in the form "12.12kWh"), but this was using 28 * 4 bytes = 112 bytes (5.4% of SRAM). I don't mind having only a single decimal point of resolution, so I changed to using uint16_t and multiplying the figure by 100. This means that 12.12 is represented as 1212, and I divide by 100 for display purposes.

The size of the array is now down to 56 bytes (much better!).

There is no trivial way to reduce the figure down to a uint8_t that I can see. I could tolerate the loss of a decimal place ("12.1kWh" instead of "12.12kWh"), but consumption is frequently higher than 25.5kWh (255 being the highest value represented by a 8-bit unsigned integer). Consumption has never been below 10.0kWh or above 35.0kWh, so conceivably I could subtract 10 from the stored figures, but I know that one day we will exceed these limits.

I then tested code to pack 9-bit values into an array. This gives a range of 0-51.2kWh and uses 32 bytes in total. However, accessing an array like this is pretty slow, especially when you have to iterate over all values to calculate an average.

So my question is - is there a more efficient way of calculating a moving average with three windows - lifetime, 28 days and 7 days? Efficiency means smaller in terms of SRAM usage, but without the penalty of huge code. Can I avoid storing all values?
If your data has low standard deviation, then one method would be to sum values over the window, and then keep subtracting the mean from the sum, while adding the new value.

This would work well if there are no outliers, thereby leading to the aggregate error tending to zero over time.

//Pseudocode

count=0
while new_reading and count&lt;7:
    sum += new_reading        //Calculate the sum of first 7 values
    count++

while new_reading:            //Loop till new readings available
    avg = sum / 7             //Calculate average
    sum -= avg                //Subtract average from sum
    sum += new_reading        //Add next reading to sum
    print avg