Peter is a DZone MVB and is not an employee of DZone and has posted 161 posts at DZone. You can read more from them at their website. View Full User Profile

Different Results When Summing a double[]

03.12.2012
| 3781 views |
  • submit to reddit

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
Published at DZone with permission of Peter Lawrey, author and DZone MVB. (source)

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)

Comments

dieter von holten replied on Mon, 2012/03/12 - 1:56pm

what result do you get when you sort the doubles-list before adding?

what is the result when sorting by abs( d ) ?

Artur Biesiadowski replied on Mon, 2012/03/12 - 2:10pm

As long as there is double involved anywhere, it is better to stay double all the way and accept 'fuzziness' of the results. Don't compare against zero, compare Math.abs(value)<EPSILON. Always use formatters.

I remember a discussion with somebody who said we should use BigDecimal for financial calculations for options, because we are losing 13 digit after the dot in precision.Our models were valid only till around 1E-4 and we were anyway rounded to E-2 or E-3 on the output (and if you traded 1000 of the options, rounded price was multiplied by 1000, not the model price), so paying 20+ times performance penalty + lack of operators was not really a good idea...

Yes, BigDecimal has it's place as long as it is used from start till end. Still, IMHO, as soon as you do new BigDecimal(double), you are just deluding yourself into some kind of safety - you will need epsilon comparisons anyway and the rest should be handled by formatting, not by scale of BigDecimal.

Oleg Kozlov replied on Mon, 2012/03/12 - 5:33pm

For financial calculations (and other types where precision is critical)  it's best to avoid using double anywhere and stick with BigDecimal end-to-end. Avoid using "new  BigDecimal(double)" at all costs, and use "new BigDecimal(String)" instead. 

dieter von holten replied on Tue, 2012/03/13 - 4:56am

the only application of summing 'real doubles' i could think of are:

- computing zeros of riemann's zeta-function

- inside  matrix-operations

all other applications use doubles to model some technical quantity, like length, weight, energy. and those dont have much meaning in the 15th digit from the left.

when our results depend on this kind of precision, you must also be aware of the inner working of the jvm: where is it allowed to use extended precison - and where not..

having more digits in the printout of the result doesnt always mean the result is 'better'.

 

 

Peter Lawrey replied on Fri, 2012/12/21 - 4:57pm in response to: Oleg Kozlov

 In eleven years of working for financial institutions, I have yet to see one which uses BigDecimal.  If they don't use double, they might use fixed point int or long e.g. in cents instead of dollars. Some use float which I don't recommend for 99% of use cases.

If you are going to convert double to BigDecimal you are better off using BigDecimal.valueOf(double) than new BigDecimal(String)

From the Javadoc for BigDecimal.avlueOf(double)

"Translates a double into a BigDecimal, using the double's canonical string representation provided by the Double.toString(double) method.

Note: This is generally the preferred way to convert a double (or float) into a BigDecimal, as the value returned is equal to that resulting from constructing a BigDecimal from the result of using Double.toString(double)."


Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.