Different Results When Summing a double[]
Join the DZone community and get the full member experience.
Join For FreeThe 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-14For 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
Published at DZone with permission of Peter Lawrey, DZone MVB. See the original article here.
Opinions expressed by DZone contributors are their own.
Comments