What is the most accurate way to count a sum of vector elements using std::accumulate? [duplicate]

Question

Possible Duplicate:
C++ float precision question

I've got a problem of determining the most precise method of the three to calculate the sum of vector elements, which can be only positive numbers, using std::accumulate.

1)

double sum(vector<float> &v)
{
     return accumulate(v.begin(), v.end(), 0.0);
}

2)

double sum(vector<float> &v)
{
     sort(v.begin(), v.end());
     return accumulate(v.begin(), v.end(), 0.0);
}

3)

double sum(vector<float> &v)
{
     sort(v.begin(), v.end(), greater<float>());
     return accumulate(v.begin(), v.end(), 0.0);
}

This is a kind of job interview question, that's why I got these particular three ways to calculate the sum. I've done a lot of searching the web, but couldn't figure out the difference. Could you please help me guys understand it?

Answer 1

The difference should be really small, but starting with the smaller numbers will be slightly more accurate. Consider for exposition purposes that your floating point number contained only 4 significant digits and an exponent, and that it was decimal rather than binary. Using the numbers:

a = 5000
b = 5000
c = 1000e4 (10000000)

If we add c first, then either a or b, the smaller of the two falls off the representation and is rounded. The end result of c + b + a will yield 1000e4. If on the other hand, we add a and b first we get 1e4 as the first intermediate value, and adding that to c will yield 1001e4 which is a more precise result for the operation.