The Britney Spears Problem(americanscientist.org)

44 pointsby edw519vor 17 Jahren7 comments

http://www.americanscientist.org/issues/id.3822,y.0,no.,content.true,page.1,css.print/issue.aspx

2 comments

Sam_Odiovor 17 Jahren

> ... 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.

ramchipvor 17 Jahren

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.

hack_eduvor 17 Jahren

You guys are so goddamn geeky! <3

3ijsflksflkvor 17 Jahren

constant space ftw

Boxervor 17 Jahren

Let average-so-far=a, count=c. When you add a new item x, the new average is: a = a + (x-a)/(c+1)

ajkirwinvor 17 Jahren

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?

jlhamiltonvor 17 Jahren

I posted this a while back, but it didn't get many votes.

http://news.ycombinator.com/item?id=243270