2010/01/11

Incremental average calculation

To calculate the average of some numbers, we can use the following simple formula:
It works in most cases, but let's suppose that we would like to know the average of a fast growing set of numbers.



Using the formula above can be problematic:
  • When a new number is added to the data set, we have to sum all numbers to calculate the current average. As the data set grows large, it takes more and more time to evaluate the formula above.
  • The algorithm based on this formula is numerically unstable: the sum of the numbers may overflow, even if the resulting average would not (see the unit test testNumericalStability).

Fortunately we can easily transform the formula to an "incremental" form:


This new form is almost as easy to implement as the original, but has two important advantages:
  • It can be used to calculate the average incrementally (the current average is calculated from the current value and the previous average).
  • It is numerically stable (see the unit test testNumericalStability).

Resources:

3 comments: