Numerical issue with `foldl` and `foldr` in Haskell

Question

I have the following Haskell script which computes the function f(x) = (2- x) - (2^3 - x^3/12)

calc x = (x - (x ^ 3) / 12)
calc2 x = (calc 2) - (calc x)

calcList1 :: [Float] -> Float
calcList1 l = foldl (+) 0.0 (map calc2 l)

calcList2 :: [Float] -> Float
calcList2 l = foldr (+) 0.0 (map calc2 l)

test1 :: Float -> Float
test1 step = (calcList1 l) - (calcList2 l) 
    where 
        l = [0.0,step..2.0]

Function calcList1 and calcList2 run calc2 function on each of list and then uses foldl and foldr respectively to sum the list. I was expecting both function to return the same answer but it does not.

*Main> test1 0.1
9.536743e-7
*Main> test1 0.01
2.2888184e-5
*Main> test1 0.001
2.4414063e-4
*Main> test1 0.0001
-3.7109375e-2
*Main>

Now I am confused. I can't see why numerical issues has to be involved here. Fold are essentially how ones collect each element which should be same in both cases, right?

What every computer scientist should know about floating point. — leftaroundabout
Keep in mind that for many applications, you don't actually need to use Float, but will be ok (or even better off) using Rational instead. — kosmikus
@kosmikus: yes, but for many applications, you don't actually need to use Rational, but will be ok (and better off, provided you know the quirks) using Double instead. — leftaroundabout
@leftaroundabout Of course there are use cases for Float and Double, but Rational is in my experience much less widely known, and I've seen many times that people unnecessarily jump to Double simply because a number has a dot in it. — kosmikus

Marco13 Marco13 · Accepted Answer · 2014-01-30T11:25:27

In general, the order in which floating point values are added is important. An entry point for own research could be http://en.wikipedia.org/wiki/Loss_of_significance . To summarize the basic caveat, in an oversimplified form:

Due to the limited number of significant bits, you have to assume something like

 100000000000000000.0 + 1.0 = 100000000000000000.0

in floating-point computations. Consequently, when computing

  100000000000000000.0 
+                  1.0 
- 100000000000000000.0

the result will be 0.0 - and thus, be different from

  100000000000000000.0 
- 100000000000000000.0
+                  1.0

where the result will be 1.0.

Numerical issue with `foldl` and `foldr` in Haskell

1 Answers