News for hackers. Stuff that matters.
Re:The Median of a Trillion Numbers by roundsquare on Monday August 24, 2009 @04:43AM (#781765)
Eh? Thats not true.

The only time this would work is if the distribution of the numbers was symmetric (or close to symmetric).

If you have

1 --> 599,999,999,999 times

4 --> 1 time

10 --> 400,000,000,000 times

Your average will be about 4.6 (a little higher) and your algorithm will return 4 as the answer when it should be 1.

Re:The Median of a Trillion Numbers by jfoutz on Monday August 24, 2009 @10:33AM (#782198)
Yeah, I commented right before bed. I thought of a bunch of problems with the average while trying to get to sleep.

I was thinking since the size of an outlier is constrained by fitting in 4 bytes, there must be a way to show the median is in some band of numbers around the average. I didn't think of a particularly useful algorithm though.

Thanks.