News for hackers. Stuff that matters.
Re:The Britney Spears Problem by Sam_Odio on Tuesday May 05, 2009 @08:14PM (#594943)
> ... calculating the average (or arithmetic mean) of a stream's integers takes three registers and three operations per integer. One register counts the elements, another records their sum, and the third register holds the value of the average, calculated as the quotient of the sum and the count.

Here's an easy brain teaser: do the above using only two registers.

Re:The Britney Spears Problem by ramchip on Wednesday May 06, 2009 @12:10AM (#595168)
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.

Re:The Britney Spears Problem by hack_edu on Wednesday May 06, 2009 @10:56AM (#595848)
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
Re:The Britney Spears Problem by Boxer on Wednesday May 06, 2009 @12:23AM (#595184)
Let average-so-far=a, count=c. When you add a new item x, the new average is: a = a + (x-a)/(c+1)
Re:The Britney Spears Problem by ajkirwin on Tuesday May 05, 2009 @10:19PM (#595062)
You could.. multiply the average register by the count register, then add the new integer to the average register, increment the count register and then re-divide?