# Accurate summation of mixed-sign floating-point values

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.

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