# 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?

• Do you want to calculate a moving average over specific windows or an estimate/approximation of the average would do? – asheeshr Mar 7 '14 at 9:19
• I want a moving average over a 7 day and 28 day window. – Cybergibbons Mar 7 '14 at 9:22
• you could use a resolution of 0.2kWh (divide and multiply with factor 5) and you still get 0-51.2kWh range in 8 bits – ratchet freak Mar 7 '14 at 14:27
• You might end up putting strings and other constants in external RAM or external Flash -- see "What can I do if I run out of Flash memory or SRAM?". – David Cary Nov 23 '14 at 5:51

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
sum += new_reading        //Calculate the sum of first 7 values
count++

avg = sum / 7             //Calculate average
sum -= avg                //Subtract average from sum
print avg
``````

you can use a different method, you keep the current average and then do

``````average = (weight1*average+weight2*new_value)/(weight1+weight2);
``````

it's not a true rolling average and has different semantics, but it may fit your needs nonetheless

for a more efficient calculation method for your 9 bits per value solution you could keep the 8 highest bits of the values in an array and separate out the least significant bits:

``````uint8_t highbits;
uint32_t lowbits;
``````

to set a value you need to split it out

``````void getvalue(uint8_t index, uint16_t value){
highbits[index] = value>>1;
uint32_t flag = (value & 1)<<index;
highbits|=flag;
highbits&=~flag;
}
``````

resulting in 2 shifts an AND and an OR and a not

to calculate the average you can use various bit tricks to speed it up:

``````uint16_t getAverage(){
uint16_t sum=0;
for(uint8_t i=0;i<28;i++){
sum+=highbits[i];
}
sum<<=1;//multiply by 2 after the loop
sum+=bitcount(lowbits);
return sum/28;
}
``````

you can use an efficient parallel bitcount for the `bitcount()`

• Can you explain more how this would allow me to calculate the 7 and 28 day average? – Cybergibbons Mar 7 '14 at 9:23
• I've used this approach for smoothing noisy analog values before, and it was certainly fairly effective. I didn't need a lot of precision though, as the resulting values were being put through a very coarse quantiser. I also didn't need historical averages. – Peter Bloomfield Mar 7 '14 at 9:26
• This doesnt allow calculating the average for a specific window. – asheeshr Mar 7 '14 at 9:27
• @Cybergibbons you can use different weights to approximate the window so old values become insignificant earlier or later, or keep 7 days for the 7 day window and this moving average for the 28 day average – ratchet freak Mar 7 '14 at 9:31

How about only storing the difference from the previous value? In electronics there is a similar concept called Delta Sigma converter, which is used for DA/AD converters. It relies on the fact that the previous measurement is reasonably near the current one.

• Another interesting idea. Unfortunately I am not sure energy consumption will always be like this, as it is a heat pump system and one day could take 30kWh, the next 10kWh. I really need to gather data and see. – Cybergibbons Mar 7 '14 at 18:28

Why couldn't you just add the values together as soon as you obtain them. So what I mean is you get the value for day 1, you divide it by 1 and store it and the 1 somewhere. Then you multiply the 1 by the value and add it to the next value and divide them both by 2.

Doing this method would create a rolling average with two or three variable as I can think of. I would write some code but I am new to stackexchange so please bear with me.

• I don't understand how this deals with the 7 day and 28 day window? – Cybergibbons Mar 8 '14 at 6:31
• Keep track of the previous and next values and keep adding and subtracting them from your running average... – Aditya Somani Mar 8 '14 at 7:16
• So then I am back in the state of needing to remember 27 days of history, surely? – Cybergibbons Mar 8 '14 at 7:17
• I've been thinking and you are right. So that technically makes my answer incorrect. I'm investing some more time and patience into it. Maybe something out of the box. I'll let you know if I come up with something. We do something like this a lot at my workplace. Let me ask around. Sorry about the confusion. – Aditya Somani Mar 8 '14 at 17:15

is there a more efficient way of calculating a moving average with ... 28 days and 7 days? ... needing to remember 27 days of history ... ?

You might get close enough storing 11 values rather than 28 values, perhaps something like:

``````// untested code
// static variables
uint16_t daily_energy; // perhaps in units of 0.01 kWh ?
uint16_t weekly_energy; // perhaps in units of 0.1 kWh ?

void print_week_status(){
Serial.print( F("last week's total energy :") );
Serial.println( weekly_energy );
int sum = 0;
for( int i=0; i<4; i++ ){
sum += weekly_energy[i];
};
Serial.print( F("Total energy over last 4 complete weeks :") );
Serial.println( sum );
int average_weekly_energy = sum/4;
int average_daily_energy = average_weekly_energy/7;
Serial.print( F("Average daily energy over last 4 weeks :") );
Serial.println( average_daily_energy );
}
void print_day_status(){
Serial.print( F("Yesterday's energy :") );
Serial.println( daily_energy );
Serial.print( F("average daily energy over the last 7 complete days: ") );
int sum = 0;
for( int i=0; i<7; i++ ){
sum += daily_energy[i];
};
int average = sum/7;
Serial.println( average );
}
``````

In other words, rather than storing every detail of every day for the last 27 days, (a) store 7 or so values of detailed daily information for the past 7 or so days, and also (b) store 4 or so "summarized" values of total or average information for each of the past 4 or so weeks.