4 ms·
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 purp
by edejong 11y ago
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 https://en.wikipedia.org/wiki/Pairwise_summation
- madez 11y agoThe 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.
- bazzargh 11y agoIt looks like a bad edit to the wiki. https://en.wikipedia.org/w/index.php?title=Pairwise_summation&diff=643560917&oldid=643548127 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)
- deleted 11y ago[deleted]
- alexSanchStern 11y agoPairwise 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.