[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