sum of small double numbers c++

Question

Assume that we have an array of small (about 10^(-15) ) double numbers in c++. If we calculate the sum of numbers in this array sequentially, for example

double sum = 0;
for (int i = 0; i < n; i++) sum+=array[i];

we get some value x.

But if we divide an array into some parts and then calculate the sum in each part and after this we add all the partial sums together we get some value x2, which is close to x but not exactly x. So I have lost accruacy in calculating sum.

Does someone know how to calculate the sum of small double numbers by partitioning these numbers into some parts without loosing accuracy?

Answer 1

The absolute size of the numbers is not the issue.

If you want a more accurate summation, have you considered a compensated sum? http://en.wikipedia.org/wiki/Kahan_summation_algorithm

However, if you really mean without losing any accuracy, your result will not necessarily fit in a double. If this is really what you want, you could look Algorithm 908 at http://dl.acm.org/citation.cfm?id=1824815 or similar.

Answer 2

The double numbers in the computer are stored in binary numeric system. That is why when you see a double value(in decimal notation) you in fact see the double value with some rounding(for instance 0.1 is infinite fraction). You can do the same experiment where the double values are degree of 2(for instance 2^(-30)) and then you will see that the values will match.

The reason that you observe difference when you sum the double values in different sequence is that after each calculation the result will be rounded in binary numeric system and so a little difference from the actual value will appear.