1
$\begingroup$

Due to the finite representation, floating-point addition loses significant bits. This is particularly noticeable when there is catastrophic cancellation, such that all the significant bits can disappear (e.g. $10^{-10}+10^{10}-10^{10}$).

Reordering the terms of the sum can improve accuracy. In particular, it is well-known that adding positive terms in increasing order is more accurate than otherwise, as the low-order bits are kept longer. I guess that this method is optimal or close to.

But for sums with both signs, is there a known strategy to improve the accuracy by reordering or grouping the terms ? Would separate summation of the positive and negative terms be a good idea (presumably not) ? Can we do better (with a reasonable increase in time complexity allowed) ?

Update:

I am quoting from the Higham reference given by @gammatester: "In designing or choosing a summation method to achieve high accuracy, the aim should be to minimize the absolute values of the intermediate sums ..." and " However, even if we concentrate on a specific set of data the aim is difficult to achieve, because minimizing the bound ... is known to be NP-hard".

Anyway, there seem to be good heuristics available.

$\endgroup$
2
  • $\begingroup$ Interesting question. Separate summation could still lead to cancellation if the sum is close to 0. $\endgroup$ – flawr Apr 29 '16 at 7:19
  • $\begingroup$ @flawr: certainly. anyway, different orders yield more or less accurate results. $\endgroup$ – Yves Daoust Apr 29 '16 at 7:22
3
$\begingroup$

I would use compensated summation. Basically you can recover most of the error from a single floating point addition. This was noticed long time ago by e.g. Dekker, Knuth, and others.

There are a lot of references, e.g. T. Ogita, S.M. Rump, and S. Oishi, Accurate sum and dot product, SIAM J. Sci. Comput., 26 (2005), pp. 1955-1988. Available as http://www.ti3.tu-harburg.de/paper/rump/OgRuOi05.pdf

In chapter 4 of N.J. Higham, Accuracy and Stability of Numerical Algorithms, 2nd ed., Philadelphia, 2002, http://www.maths.manchester.ac.uk/~higham/asna/ compensated and other methods are described and analysed.

A simple fast method is https://en.wikipedia.org/wiki/Kahan_summation_algorithm

$\endgroup$
1
  • 1
    $\begingroup$ WOW: this is a dream answer ;-) $\endgroup$ – Yves Daoust Apr 29 '16 at 7:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.