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

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

On 25 September 2014 18:54, Carter Schonwald 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.)