sum of series using float

Question

I calculated the first 20 elements of the series -

in 2 ways , 1st - forward , 2nd - backward. For this I did -

#include <iostream>
#include <math.h>
using namespace std;

float sumSeriesForward(int elementCount) {
    float sum = 0;
    for (int i = 0; i < elementCount; ++i) {
        sum += (float) 1 / (pow(3, i));
    }
    return sum;
}

float sumSeriesBack(int elementCount) {
    float sum = 0;
    for (int i = (elementCount - 1); i >= 0; --i) {
        sum += (float) 1 / (pow(3, i));
    }
    return sum;
}

int main() {
    cout.precision(30);
    cout << "sum 20 first elements - forward: " << sumSeriesForward(20) << endl;
    cout << "sum 20 first elements - back: " << sumSeriesBack(20) << endl;
}

And I got -

sum 20 first elements - forward: 1.5000001192092896
sum 20 first elements - back: 1.5

Can someone please explain why is the difference between the 2 ways ?

Answer 1

In general, floating point numbers cannot represent values exactly. When you operate on the values errors propagate. In your example, when computing backwards you add small values to ever bigger numbers, having a good chance that the sum of the small numbers so far has an effect on the bigger number. On the other hand, when you compute forward you start with the big numbers and the smaller numbers have ever less effect on it. That is, when summing you always want to sum smallest to biggest.

Just consider keep a sum in just a fixed number of digits. For example, keep 4 digits and sum these numbers top to bottom and bottom to top:

values   top to bottom   bottom to top
10.00      10.00            10.01
0.004      10.00            0.010
0.003      10.00            0.006
0.002      10.00            0.003
0.001      10.00            0.001

Floating point numbers work just the same way, using a fixed number of [binary] digits.

Answer 2

To improve accuracy when summing numbers, consider the Kahan summation algorithm. This significantly reduces the error compared to the obvious approach (including summing numbers from smallest to greatest).