Who has actually run into this in practice? Though I’m sure a few people have I doubt it’s more than .001% of programmers or programs. And those that do run into it are probably aware of the challenges.
Calculating the mean of a list of numbers (2016)
21–30 of 96 posts
Re: Calculating the mean of a list of numbers (2016)
#22What 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 space of precision as the original data.
Re: Calculating the mean of a list of numbers (2016)
#23Earlier quoted context omitted.
If you when calculating an average actually reach overflow in a double without messing up the precision first and making the calculation worthless in the first place, some numbers in the list of numbers is bogusly big anyway.
Or the list is just very long.
Not really. The time required to overflow that way is unrealistic. Also I think you'll run into S + x = S. at that point your sum will stop climbing towards overflow.
Re: Calculating the mean of a list of numbers (2016)
#24This 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?
Almost always they ignore this kind of issue; the best you're likely to get is a mean() function that remembers to sort the input first. Most numbers are in a "human" range far from the limits.
Re: Calculating the mean of a list of numbers (2016)
#25An 'online' mean calculation might resolve some of the common issues. Something like - def mean(ls): mu = 0.0 for i, x in enumerate(ls): mu = i/(i+1) * mu + x/(i+1) return mu
How is that different from the second example?
Re: Calculating the mean of a list of numbers (2016)
#26An 'online' mean calculation might resolve some of the common issues. Something like - def mean(ls): mu = 0.0 for i, x in enumerate(ls): mu = i/(i+1) * mu + x/(i+1) return mu
How much precision loss is to be expected here?
It is proportional to the number of terms in the sum. Kahan summation has a tighter error bound.
Re: Calculating the mean of a list of numbers (2016)
#27An 'online' mean calculation might resolve some of the common issues. Something like - def mean(ls): mu = 0.0 for i, x in enumerate(ls): mu = i/(i+1) * mu + x/(i+1) return mu
How much precision loss is to be expected here?
Good point. The precision loss will be pretty bad if the numbers added above have greatly different magnitudes, which could occur if the next number (x) is very different to the current mean (mu), or if the list is very long. The first issue could be partially mitigated by sorting the list first. If the list is very long, the above algorithm will necessarily add numbers of quite different magnitudes, but employing something like Kahan summation - https://en.wikipedia.org/wiki/Kahan_summation_algorithm , could partially mitigate that issue as well.
Re: Calculating the mean of a list of numbers (2016)
#28An 'online' mean calculation might resolve some of the common issues. Something like - def mean(ls): mu = 0.0 for i, x in enumerate(ls): mu = i/(i+1) * mu + x/(i+1) return mu
How is that different from the second example?
That you don't have to know the number of elements to sum at start. But I think the precision loss is even greater this way.
Re: Calculating the mean of a list of numbers (2016)
#29What 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.
Re: Calculating the mean of a list of numbers (2016)
#30So what's the correct code? I try my guess before reading the 30 page paper (I will add my comment after reading it)
My first guess: Normalize it. Find the largest exponent and divide all values with the exponent. This is a power-of-2 operation so would not lose any precision. Then divide all numbers by the length. Perform the same normalization again. Sum the numbers, then revert the exponent that was removed in the first step.
My second guess (backup plan): Use the interval arithmetic. I don't remember the specifics but I remember this is the safest form of floating point operations. But perhaps I should be careful about the performance penalty.