How about a special running average: keep the count in one register and the average in the other one. Let's say N is the current count and av the average. The algorithm is in C-style notation:
void addElement( int val ) {
++N;
av = ((N - 1) * av / N) + val / N;
}
I have used a similar trick (with a fixed N) to implement a cheap running average for an image acquisition software and it works quite well, but of course if N is very large val / N becomes negligible.
You guys are so goddamn geeky! <3
Re:The Britney Spears Problem
by 3ijsflksflk on Friday May 08, 2009 @12:37AM
(#599193)
constant space ftw
Let average-so-far=a, count=c. When you add a new item x, the new average is: a = a + (x-a)/(c+1)
Here's an easy brain teaser: do the above using only two registers.