CODEWITHSUNDEEP
c
Rob Gorman
Rob Gorman

Reputation: 3694

Calculate Average of N integers in C using only integer arithmetic and without keeping N values

I have an embedded C program in a constrained system which reads sensor measurements. I would like to calculate a running average during the last N sensor readings from the time that some event takes place. I want the calculation to use only integer operations (no floating point). Also I don't have enough storage to maintain all N readings so I want to create a running average total somehow and add to that total each time I get a new reading. One formula that I have seen to approximate this is

avg = ((avg * (n-1)) + currentReading) / n;

When I coded and tested this, however the calculated average was always less than if I add all the N readings and divided by N. How to improve this?

Upvotes: 1

Views: 2512

Answers (3)

chux
chux

Reputation: 154055

OP's code is close yet would benefit with a rounded division rather than standard integer division. So add a bias. The bias depends on the sign of the operands.

// avg = ((avg * (n-1)) + currentReading) / n;
avg = (avg * (n-1)) + currentReading + bias) / n;

A 2nd problem is one of range: (avg * (n-1)) + currentReading easily overflow. The simplest solution to resort to wider math. Use a wider type

// Example, depends on system
// avg * (n-1)) + currentReading
1uLL * avg * (n-1)) + currentReading

Putting this together:

// avg = ((avg * (n-1)) + currentReading) / n;
int avg, currentReading;
int n; // n > 0
int2x numerator;  // int2x some type 2x wide as int, maybe long long

numerator = (int2x)avg * (n-1) + currentReading;  // Wider math
int bias = n/2;
if (numerator < 0) bias = -bias;
numerator += bias;

avg = (int) (numerator / n);

Upvotes: 1

stark
stark

Reputation: 13189

You can't get exactly what you want unless you keep the last N samples, but you can approximate it with:

avg = ((avg * (n-1)) + currentReading + (n/2)) / n;

This weights the current reading to have 1/n significance in the average.

Upvotes: 1

Ed Heal
Ed Heal

Reputation: 60017

Just keep the running total along the number of values - two integers required. Simple sum at the end (or whenever you want).

Upvotes: 1

Related Questions