The Britney Spears Problem

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

by edw519 • 17 years ago

44 7 17 years ago

Sam_Odio• 17 years ago

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

ajkirwin• 17 years ago

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?

ramchip• 17 years ago

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_edu• 17 years ago

You guys are so goddamn geeky! <3

3ijsflksflk• 17 years ago

constant space ftw

Boxer• 17 years ago

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

jlhamilton• 17 years ago

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

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

The Britney Spears Problem

Related Stories