How to Calculate an Average Without Storing Values | Hacker News Reader

How to Calculate an Average Without Storing Values

uptimesniper.com

3 pointshankchinaski2 comments

I suspect this has horrible numerical stability, especially if n gets large (you’re multiplying the running average by n, then tweaking it a bit, and dividing it by n+1)

On some systems, that multiplication and division also may be slow.

Even if it is stable, I think it’s better to keep track of the running sum and the number of items seen:

  sumSoFar += newItem
  numSeen += 1

and only do the division when you need the average.

The risk then is overflow for large numbers of items, but that’s no worse than the proposed algorithm. Its running value will not overflow as easily, but the intermediate value of the multiplication can do just as easily.

I think the best way would be to keep a window size or some sort of rolling average for when the dataset gets really big. Because in effect you wouldn’t care what the average over a lifetime for a website is. You would probably just want for a given window

Reply on news.ycombinator.com