Live data from Hacker News

Calculating the mean of a list of numbers (2016)

hypothesis.works

41–50 of 96 posts

Re: Calculating the mean of a list of numbers (2016)

#41
post #29
post #22

What about a "reduce" technique? Average the numbers in equal-sized chunks, then average those averages. You could even chunk the chunk averages and repeat the process as many levels down as you want to, and chunks could be as small as 2 each. I guess this still assumes that the largest number in the original list is less than or equal to the maximum floating point value, but otherwise you stay roughly in the same sp…

Unfortunately, by averaging the averages you skew the results. Average of averages does not produce the same result as averaging the whole list.

It does if you weight the chunks correctly. Combine pairs of numbers and keep a weight of the remaining odd number. Either cut the weight in half of the odd number every time or use it in the average if an iteration has an even number of numbers.

Re: Calculating the mean of a list of numbers (2016)

#42
post #29

Earlier quoted context omitted.

Unfortunately, by averaging the averages you skew the results. Average of averages does not produce the same result as averaging the whole list.

Average of equal size chunks' averages does. (mathematically)

Ah my bad. Thanks for that correction

Re: Calculating the mean of a list of numbers (2016)

#43
post #41
post #29

Earlier quoted context omitted.

Unfortunately, by averaging the averages you skew the results. Average of averages does not produce the same result as averaging the whole list.

It does if you weight the chunks correctly. Combine pairs of numbers and keep a weight of the remaining odd number. Either cut the weight in half of the odd number every time or use it in the average if an iteration has an even number of numbers.

Thanks for that, didn't know.

Re: Calculating the mean of a list of numbers (2016)

#44
This article is both extremely insightful, and overly pedantic.

If you are not aware of how floating point value work, this is an excellent illustration of that, and you should spend some time learning about the risks and edge cases associated with working with them.

At the same time, enabling floating point exceptions on your platform is probably the most pragmatic way of dealing with these issues. until you are in a domain where this level of effort is an investment, over-engineering modules that use floating points is a waste of time.

Re: Calculating the mean of a list of numbers (2016)

#45
post #22

What about a "reduce" technique? Average the numbers in equal-sized chunks, then average those averages. You could even chunk the chunk averages and repeat the process as many levels down as you want to, and chunks could be as small as 2 each. I guess this still assumes that the largest number in the original list is less than or equal to the maximum floating point value, but otherwise you stay roughly in the same sp…

That produces an unavoidable special case when the number of elements in the list is a prime number.

Re: Calculating the mean of a list of numbers (2016)

#46
post #4

This article highlights and issue with floating point numbers, a substantial use case for data scientists (and as such, I value the input). How do REPLs and databases handle this edge case?

Data science is squishy to begin with -- those wanting high performance are heading to fixed-point hardware-accelerated solutions where loss-of-precision is a given, so not having a fully accurate answer with high-precision floating-point along many steps to solving the problem doesn't seem like a big deal.

Re: Calculating the mean of a list of numbers (2016)

#47
post #6

If you're reaching these values then it's extremely likely that either: (a) You're doing something wrong (usually, not standardizing your data, etc.) which means that you're not thinking about the fact that computers have finite numerical precision and adjusting your problem accordingly (e.g., have a wide dynamic range of numbers). Or, (b) your problem is pretty ill-conditioned and there's probably no solving it in a…

For problem (b), this is the standard case for inverse problems, which are almost always ill-posed / ill-conditioned. There is now a vast literature on this subject, including many algorithms for solving them robustly.

"...incorrectly posed problems were considered ‘taboo’ for generations of mathematicians, until comparatively recently it became clear that there are a number of quite meaningful problems, the so-called ‘inverse problems,’ which are nearly always unstable with respect to fluctuations of input data." — H. Allison, Inverse Unstable Problems and Some of Their Applications (1979)

Re: Calculating the mean of a list of numbers (2016)

#48
For the probably simplest solution to the given problem if summing doubles there is a hardware in every x86 CPU which allows the biggest number during the computation to be 1.18e4932 (using 80 bits internally, 15 from that for the exponent, vs. only 11 in the 64-bit double). By just activating it the sum can be done very fast, and no need for any modification: first sum, then divide, convert to double at the end.

You should not use SSE for that however, but the old x87 "FPU" instructions.

Re: Calculating the mean of a list of numbers (2016)

#49
post #35
post #6

If you're reaching these values then it's extremely likely that either: (a) You're doing something wrong (usually, not standardizing your data, etc.) which means that you're not thinking about the fact that computers have finite numerical precision and adjusting your problem accordingly (e.g., have a wide dynamic range of numbers). Or, (b) your problem is pretty ill-conditioned and there's probably no solving it in a…

Most of the issues discussed in the article are not from limits in precision, they're from overflows that arise from limits in the exponential range. Finding the average of 8e+307 and 8e+307 is a "low precision" problem, and even naive methods to avoid overflow will not hit limits on precision in this case (e.g. 8e+307/2 + 8e+307/2). You're right that there are issues with precision and floating point math (the artic…

Sorry, I should’ve been more clear: when I said “precision” I meant any of several things related to floating point arithmetic including, but not limited to: actual numerical precision of operations, non-associativity of operations, overflows (which affects the latter case as well), etc. (Which is why I mention dynamic range in the GP.)

The point is that there is an “unwritten contract” between the user and the library: if we want any kind of performance, then we have to promise that the inputs are “well behaved” (in a very specific sense that varies from algorithm to algorithm). The user knows this and so does the developer, because otherwise most algorithms will spend most of the actual compute time converting problems to “fully general forms” that work on every input, but are hundreds if not thousands of times slower than the original.[0]

The point is that most people want “mean” to be fast, and a simple implementation of mean will work on almost every case, without needing to resort to arbitrary precision fractional arithmetic. The claim I make above is that the latter thing is almost never what people need, because if they did then almost every numerical algorithm is doomed from the start, whenever they perform operations that are more complex than “take the mean.” Now, if they really need this to be done for the huge numbers given (or whatever the case is), then there are libraries that will do this at a huge cost in performance. (But, if they really did need it—for example, when a problem cannot be rewritten in a simple way that would work with the available implementations—my bet is that this user would know).

Also apologies for mistakes, I’m currently on my phone walking to a meeting.

——

[0] that isn’t to say that if you can write a fast and general version, that you shouldn’t! Just that it usually incurs some overhead that is often unacceptable (see, e.g. using arbitrary precision fractions for Gaussian elimination).

Post reply on HN