Calculating the mean of a list of numbers (2016) • Hacker News Board

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

#61

Post by vortico » Sat, Mar 23, 2019, 7:58 PM UTC

The reason exponents have so many bits is basically to solve this problem. The exponent/mantissa bits of IEEE 754 double could have been 8 and 55, but I suppose the standard committee decided that some precision should be sacrificed to allow stupid values outside the range of meaningful physical numbers so that you never have to worry about the problem mentioned in this article. So if you pretend that doubles have 8 exponent bits as they probably should have been, then `sum(list) / len(list)` will always work for this set of "sane" values.

And if that isn't enough, you have subnormal numbers as a safety net as well, although using these kills performance on many FPUs.

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

#62

Post by GregBuchholz » Sat, Mar 23, 2019, 8:39 PM UTC

wglb wrote: post #31

kazinator wrote: post #15

This is the TXR Lisp interactive listener of TXR 214. Quit with :quit or Ctrl-D on empty line. Ctrl-X ? for cheatsheet. 1> (defun mean (seq) (/ (sum seq) (len seq))) mean 2> (mean '(8.988465674311579e+307 8.98846567431158e+307)) ** out-of-range floating-point result ** during evaluation at expr-1:1 of form (sum seq) Works for me; error is caught. Breaking news: floating-point has a limited range! Detailed story at 11…

Similar correct result from sbcl.

The pedantic point of the article is that an error in this situation isn't correct. The average is 8e307 and 8e307 is 8e307.

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

#63

Post by acqq » Sat, Mar 23, 2019, 8:43 PM UTC

acqq wrote: post #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…

And if you have to use Microsoft or Intel C compiler for 64-bits Windows, you have to use assembly to reach that functionality which is still in the CPU. With the open source compilers it's better. You can write C code that works with both GCC and clang.

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

#64

Post by adrianmonk » Sat, Mar 23, 2019, 8:43 PM UTC

praptak wrote: post #50

Calculating (a+b)/2 isn't even entirely trivial for integers - the trivial implementation overflows on large numbers, as one may find out when doing a binary search over a 4GB array.

Also, their overflow avoidance technique fails on integers too, and for basically the same reason (lack of precision).

Suppose you want to find the mean of (1, 1, 1). If you divide by the length of the list first, you're going to compute sum(1/3, 1/3, 1/3), which reduces to sum(0, 0, 0). And 0 < min(1, 1, 1).

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

#65

Post by wglb » Sat, Mar 23, 2019, 8:48 PM UTC

avian wrote: post #53

tntn wrote: post #40

Earlier quoted context omitted.

> Thus, you should sort an array of floating point numbers and begin the summation with the smallest Is this method more accurate than Kahan summation? And if so, is it worth the extra cost of sorting?

No, in fact it's slower than Kahan summation and less accurate. In particular, sorting doesn't help if you sum up a large number of similarly small values.

How is it less accurate?

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

#66

Post by pjungwir » Sat, Mar 23, 2019, 8:58 PM UTC

I wrote a Postgres extension to compute the mean of an array of floats. [0] I tried to avoid overflow problems by using an approach that finds the final mean for each element as it goes along. [1] But that is a lot of divisions, so there is a disappointing perf hit. (It's still a lot faster than SQL though. :-) I'd love to know if there is a faster way that is still correct. (I have some implementations for SSE2 and AVX that aren't published yet, but they still do all the divisions; what I really want is a different algorithm.)

[0] https://github.com/pjungwir/aggs_for_arrays [1] https://github.com/pjungwir/aggs_for_arrays/blob/master/arra...

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

#67

Post by nestorD » Sat, Mar 23, 2019, 9:00 PM UTC

As commented by others, this is the kind of functions for which you want to use a numerically stable algorithm.

For that you can :

- sort the numbers (clearly not the most cost effective solution but easy),

- use a high precision accumulator (which can give you an exact result if you go far enough),

- use a compensated summation (such as Kahan summation but the state of the art can do much better)

For extreme cases there are algorithms that can give you an exact result, my current favorite being Accurate Floating-Point Summation Part I: Faithful Rounding : https://www.researchgate.net/publication/228664006_Accurate_...

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

#68

Post by bjoli » Sat, Mar 23, 2019, 9:10 PM UTC

wellpast wrote: post #60

And then there was Clojure... (defn average [numbers] (/ (apply + numbers) (count numbers))) (average [8.988465674311579e+307M, 8.98846567431158e+307M]) => 8.9884656743115795E+307M

But by then you are not comparing apples to apples. Those are Java BigFloats, and by that reasoning Java and any other language that has access to bigfloats also would do the correct thing.

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

#69

Post by wellpast » Sat, Mar 23, 2019, 9:38 PM UTC

bjoli wrote: post #68

wellpast wrote: post #60

And then there was Clojure... (defn average [numbers] (/ (apply + numbers) (count numbers))) (average [8.988465674311579e+307M, 8.98846567431158e+307M]) => 8.9884656743115795E+307M

But by then you are not comparing apples to apples. Those are Java BigFloats, and by that reasoning Java and any other language that has access to bigfloats also would do the correct thing.

But still relevant, no?

You could say that the “hard problem” mentioned has been removed by those abstractions.

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

#70

Post by tntn » Sat, Mar 23, 2019, 9:43 PM UTC

wglb wrote: post #65

avian wrote: post #53

Earlier quoted context omitted.

No, in fact it's slower than Kahan summation and less accurate. In particular, sorting doesn't help if you sum up a large number of similarly small values.

How is it less accurate?

Using avian's example of a list of numbers of similar magnitude, sorting the numbers will not really be any better than just summing them directly, but Kahan summation will do better.