[Haskell-cafe] Sum and Product do not respect the Monoid laws

Richard A. O'Keefe ok at cs.otago.ac.nz
Fri Sep 26 12:06:37 UTC 2014


On 26/09/2014, at 10:33 PM, Jason Choy wrote:

> On 25 September 2014 18:54, Carter Schonwald <carter.schonwald at gmail.com> wrote:
> No.  It is associative, just not in the way you expect.  😄
> 
> From What Every Computer Scientist Should Know About Floating-Point Arithmetic by David Goldberg: "Due to roundoff errors, the associative laws of algebra do not necessarily hold for floating-point numbers. For example, the expression (x+y)+z has a totally different answer than x+(y+z) when x = 10^30, y = -10^30 and z = 1 (it is 1 in the former case, 0 in the latter)."

Knuth Volume 2, second edition:

  (u [*] v) [*] w = uvw(1+d1)(1+d2)
  u [*] (v [*] w) = uvw(1+d3)(1+d4)

where each |di| < 1/2 b**(1-p), so

   (u [*] v) [*] w
   --------------- = 1 +  d
   u [*] (v [*] w)

where |d| < 2 b**(1-p)/(1 - 1/2 b**(1-p))**2
           = 2 ulp/(1 - 1/2 ulp)**2

subject to certain caveats.  It's not unfair to say that
floating point multiplication is (nearly) associative
"within a few ulp".

Goldberg's example involves addition, not multiplication.
(Checking addition of numbers *with the same sign* is left
as an exercise for the reader.)



More information about the Haskell-Cafe mailing list