Saturday, February 16, 2013

What's the point?

Floating point is notoriously tricksy but this little gotcha was new to me.

Unlike normal maths, floats are not associative under addition. For instance:

        System.out.println(((1.0f + 0.05f) + 0.05f) == (1.0f + (0.05f + 0.05f)));



as most programmers might know. This is because although the maximum and minimum for positive floats are something like 3.4028235E38 and 1.4E-45 respectively, not all numbers can be expressed. For instance, "the decimal fraction 0.1 cannot be precisely represented in binary" [1].

OK, so much you should know. But here's the gotcha. Adding a series of numbers that can be represented with floating points might give you a different answer if you go from the last to the first rather than the first to the last.

To demonstrate, let's make an array with the first value much larger than the others.

        private float[] createFloatArray() {
                int     number          = 101;
                float[] floats          = new float[number];
                float   lowValue        = 1f;
                for (int i = 1 ; i < floats.length ; i++) {
                        floats[i] = 1f;
                floats[0] = 1E8f - (number * lowValue);
                return floats;

Then we add up the floats in the array from left to right:

        private float totalLeftToRight(float[] floats) {
                float totalLeftToRight = 0;
                for (int i = 0 ; i < floats.length ; i++) {
                        totalLeftToRight += floats[i];
                System.out.println("Total (left to right): " + new BigDecimal(totalLeftToRight));
                return totalLeftToRight;

Then compare that answer to adding the array right to left (similar code but not worth printing here) and you get:

Total (left to right): 99999896
Total (right to left): 100000000

The reason is that all the small numbers added together are significant when then added to the large number. But individually, they are too small to care about.

As the value of a floating point get bigger, the gaps between numbers that can be expressed also increases. 

Note how (1E8 - 101) cannot be expressed as a float either. It comes to 99999896 rather than 99999899.

[1] Roedy Green has a good description of floating points here.

No comments:

Post a Comment