Over a million developers have joined DZone.

Different Results When Summing a double[]

· Java Zone

Discover how AppDynamics steps in to upgrade your performance game and prevent your enterprise from these top 10 Java performance problems, brought to you in partnership with AppDynamics.

The order you add double values can give you different results. This gets worse as the sum approaches 0 as the error is large compared with the result. Something I found interesting recently is seeing how many possible results you can get depending on the order you sum the values.

Looking at variations on the sum

In the following code, the program creates random numbers around zero, adding a value to the list which ensures the sum is almost zero. It lists the different sums it finds.

List doubles = new ArrayList();
Random rand = new Random();
double sum0 = 0;
for (int i = 0; i < 1000; i++) {
    doubles.add(rand.nextDouble() - rand.nextDouble());
    sum0 += doubles.get(doubles.size() - 1);
}
doubles.add(-sum0);

SortedSet sums = new TreeSet();
for (int i = 0; i < 10 * 1000 * 1000; i++) {
    Collections.shuffle(doubles, rand);
    double sum = 0;
    for (double d : doubles)
        sum += d;
    if (sums.add(sum))
        System.out.println(sum);
}
System.out.printf("Found %,d different sums from %g to %g%n", sums.size(), sums.first(), sums.last());

prints

-1.0891287871572786E-13
5.184741524999481E-14
-1.0469403122215226E-13
-1.1235457009206584E-13
3.985700658404312E-14
  ... many snipped ...
-1.042499420123022E-13
7.37188088351104E-14
-1.1379786002407855E-13
-1.084687895058778E-13
-1.0591527654923993E-13
Found 1,411 different sums from -1.39000e-13 to 7.37188e-14
For an array of 100, it found 156 possible sums. For 10,000 values you can get
Found 12,701 different sums from -8.01137e-13 to 1.59517e-12

To get an exact answer you can use BigDecimal. This will give you same result regardless of order.

BigDecimal bd = BigDecimal.ZERO;
for (double d : doubles)
    bd = bd.add(new BigDecimal(d));
Collections.shuffle(doubles, rand);
BigDecimal bd2 = BigDecimal.ZERO;
for (double d : doubles)
    bd2 = bd2.add(new BigDecimal(d));
if (!bd.equals(bd2))
    throw new AssertionError();
System.out.println("The actual sum is exactly "+bd);

and prints something like

The actual sum is exactly 4.77395900588817312382161617279052734375E-15

The Java Zone is brought to you in partnership with AppDynamics. AppDynamics helps you gain the fundamentals behind application performance, and implement best practices so you can proactively analyze and act on performance problems as they arise, and more specifically with your Java applications. Start a Free Trial.

Topics:

Published at DZone with permission of Peter Lawrey , DZone MVB .

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}