Re: Does the order matter to add a sequence of floating numbers

On Oct 30, 12:59 pm, user923005 <dcor...@xxxxxxxxx> wrote:
On Oct 30, 9:29 am, Richard Heathfield <r...@xxxxxxxxxxxxxxx> wrote:

JosephLee said:

Let's say float arr[100], we want to add them up, does the order
matter? what is the different between arr[0] +..+ arr[99], and
arr[99]+...+arr[0]?

You wouldn't think it would make a difference, would you? But it can,
nevertheless, especially when some or all of the values are near the
limits of what can be represented.

I tried fairly hard to write a program to demonstrate this, and failed. :-)

Take 2 and add DBL_EPSILON to it 1 million times.
Then, take DBL_EPSILON, add it up 1 million times, and add 2 to it.

In general, the most accurate way to add floating point numbers is
from smallest to largest.

You can get nearly the same accuracy by using Kahan's compensated
summation (Kahan's adder).
[snip kahan adder implementation]

Here is sample output:

#include <iostream>
#include <iomanip>
#include <cfloat>
using namespace std;

#include "kahan.hpp"

int main(void)
{
KahanAdder < double >ksb,
ksa;
double nsb = 0,
nsa = 0;
size_t index;

for (index = 0; index < 1000000; index++) {
ksb += DBL_EPSILON;
nsb += DBL_EPSILON;
}
ksb += 2.0;
nsb += 2.0;

ksa += 2.0;
nsa += 2.0;

for (index = 0; index < 1000000; index++) {
ksa += DBL_EPSILON;
nsa += DBL_EPSILON;
}
cout << setprecision(DBL_DIG);
cout << "double sum, adding largest first = " << nsb << endl;
cout << "kahan sum, adding largest first = " << ksb << endl;
cout << "double sum, adding largest last = " << nsa << endl;
cout << "kahan sum, adding largest last = " << ksa << endl;
return 0;
}
/*
C:\tmp>kahantest
double sum, adding largest first = 2.00000000022204
kahan sum, adding largest first = 2.00000000022204
double sum, adding largest last = 2
kahan sum, adding largest last = 2.00000000022204
*/

.