Good (simple) approximation to the arithmetic mean in integer arithmetic

Question

I appreciate this is a bit of an open ended question that might veer off towards opinion and not rigour but I hope it's interesting enough to be thought suitable.

Recently I had to write some code to calculate the arithmetic mean of a long run of observed values. Super-accuracy was not too important - being able to see a reasonable approximation of the current value and the longer-term trends were important.

A previous implementation had worked on the basis of:

NewMean = (OldMean x (Observations - 1) + NewObservation)/Observations

Which is obviously correct but is in danger of overflowing as the product of means and observations grows.

I looked for a canonical replacement in Knuth's The Art of Computer Programming but he doesn't discuss this in terms of integer maths at all, but does suggest a simple recurrence relation using floating point - and I adopted a version of this:

NewMean = OldMean + (NewObservation - OldMean)/Factor

I set Factor as 20 and generate the first 20 means in the old way before switching to this.

As the observations are about 3 orders of magnitude greater than Factor it works reasonably well (though obviously I lose precision) - but is there a better way that is neither very computationally intensive nor likely to overflow?

Answer 1

The second formula is simply a rearrangement of the first, and what you're calling "factor" should simply be the number of observations. Setting the factor equal to $20$ forever instead is just a way of weighting new observations more heavily than old ones, which I take it is not what you want.

Let the old mean be $\mu$, the new observation be $x$, and the total number of observations $n$. Then $$ \frac{\mu \cdot (n-1) + x}{n} = \mu \cdot \frac{n-1}{n} + \frac xn = \mu - \frac \mu n + \frac xn = \mu + \frac{x-\mu}{n}. $$ If we were doing the calculations with real numbers, both formulas would be exact. The only way to improve over rounding at each step would be to keep track of $(x-\mu) \bmod n$, and try to save it in some running total of fractional parts, which is difficult and not worth it in my opinion.

One improvement I have to suggest is language-dependent. If you're using a programming language where 7/5 gives 1 but (-7)/5 gives 2, then integer division always rounds down, introducing a bias which is slight but easy to correct for: just replace $\frac{x-\mu}{n}$ by $\frac{x-\mu + n/2}{n}$ to round to the nearest integer. If you're using a language where 7/5 gives 1 and (-7)/5 gives -1, this is not necessary. But this is a very minor correction either way.

Answer 2

Look up Kahan's method for computing running mean and variance. It computes it quite accurately at the expense of some additional computation.