News for hackers. Stuff that matters.
Re:Improving Floating Point Accuracy: A Look at Sums by acqq on Monday October 19, 2015 @04:42AM (#10411805)
It just uses:

https://en.wikipedia.org/wiki/Kahan_summation_algorithm

And Wikipedia has also a discussion of how some compiler optimizations can optimize the algorithm implementation wrong.

Re:Improving Floating Point Accuracy: A Look at Sums by edejong on Monday October 19, 2015 @06:09AM (#10412021)
Indeed. My advice is to use pairwise summation [0], which is easier to implement, does not suffer from compiler optimizations and is, for normal means and purposes, sufficiently precise. Previously, I considered a small blog-post, but it would be an (incomplete) copy of a Wikipedia article.

[0] https://en.wikipedia.org/wiki/Pairwise_summation

Re:Improving Floating Point Accuracy: A Look at Sums by alexSanchStern on Monday October 19, 2015 @02:32PM (#10414661)
Pairwise summation is definitely a useful technique, depending on your situation. However, it does have the key limitation that you need to have all your data beforehand. There are quite a few cases in practice where you have streaming data, and Kahan summation handles this just fine. In addition, if your data is really unbalanced in it's magnitudes, pairwise summation can still lose a fair amount of precision compared to Kahan summation. There are definitely cases where you'd want to use one, and cases where you'd want to use the other.
Re:Improving Floating Point Accuracy: A Look at Sums by madez on Monday October 19, 2015 @11:49AM (#10413638)
The argumentation in the article is bad at some points. First, it praises the fast execution of pairwise addition with a large base case. Second, it praises pairwise addition as accurate with O(E) in the base case. Following this argumentation, making the base case as big as possible would be optimal. However, that would result in naive summation in practice. Thus, the argumentation is bad.
Re:Improving Floating Point Accuracy: A Look at Sums by bazzargh on Monday October 19, 2015 @02:02PM (#10414526)
It looks like a bad edit to the wiki.

https://en.wikipedia.org/w/index.php?title=Pairwise_summatio...

^ this user changed the error bounds, incorrectly. The worst case for the naive sum is pretty obviously epsilon*N (and is described that way on the Kahan sum page)

Re:Improving Floating Point Accuracy: A Look at Sums by wiml on Monday October 19, 2015 @12:20PM (#10413856)
I may be missing something, but since the error accumulation variable "c" is also of finite width, isn't this the same as simply computing your sums in double precision and then truncating? A pessimal input can still cause cancellation in both sum and c and leave you with an arbitrarily large error.
Re:Improving Floating Point Accuracy: A Look at Sums by benjaminl on Monday October 19, 2015 @02:38PM (#10414697)
That is what I was thinking the whole article. Seem like not only would that be simpler it would also be faster. I assume that there is a reason for employing this, but I couldn't find it. Looking at the paper A Comparison of Method For accurate Summation by McNamee[1], double precision beats Kahan summation, both in speed and reduction in errors.

Moving to double precision of course only holds if your variables were previously only single precision. If your variables are already double precision, I could see the reason for implementing more exotic methods.

[1] http://www.sigsam.org/bulletin/articles/147/sumnums.pdf

Re:Improving Floating Point Accuracy: A Look at Sums by alexSanchStern on Monday October 19, 2015 @02:27PM (#10414639)
Yes, that's completely true. But while there are still inputs for which terrible accuracy could result, for many of the inputs which would arise in practice, the Kahan summation technique is "good enough" to prevent loss of accuracy. The chances of getting an input for which catastrophic cancellation would result on the doubled precision are far overshadowed by the chances of getting inputs for which the normal summation would have unacceptable loss accuracy, but Kahan summation would not.