A bug with Sum (as in Monoid)

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

A bug with Sum (as in Monoid)

Dannyu NDos
Sum has bug with floating points. Current definition states +0 as the identity element, while the actual identity is -0 since +0 + -0 = +0.

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: A bug with Sum (as in Monoid)

Brent Yorgey
How is that worse than the fact that addition is already not associative for floating point types?  At least +0 is really the identity up to (==).

On Wed, Nov 6, 2019, 3:49 PM Dannyu NDos <[hidden email]> wrote:
Sum has bug with floating points. Current definition states +0 as the identity element, while the actual identity is -0 since +0 + -0 = +0.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: A bug with Sum (as in Monoid)

Dannyu NDos
Omg, addition is not even associative? The zeros truly ruined everything.

2019년 11월 7일 (목) 06:58, Brent Yorgey <[hidden email]>님이 작성:
How is that worse than the fact that addition is already not associative for floating point types?  At least +0 is really the identity up to (==).

On Wed, Nov 6, 2019, 3:49 PM Dannyu NDos <[hidden email]> wrote:
Sum has bug with floating points. Current definition states +0 as the identity element, while the actual identity is -0 since +0 + -0 = +0.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: A bug with Sum (as in Monoid)

Brent Yorgey
Hint: the problem has nothing to do with zeros.

λ> 0.1 + (0.2 + 0.3) == (0.1 + 0.2) + 0.3
False


On Wed, Nov 6, 2019 at 4:20 PM Dannyu NDos <[hidden email]> wrote:
Omg, addition is not even associative? The zeros truly ruined everything.

2019년 11월 7일 (목) 06:58, Brent Yorgey <[hidden email]>님이 작성:
How is that worse than the fact that addition is already not associative for floating point types?  At least +0 is really the identity up to (==).

On Wed, Nov 6, 2019, 3:49 PM Dannyu NDos <[hidden email]> wrote:
Sum has bug with floating points. Current definition states +0 as the identity element, while the actual identity is -0 since +0 + -0 = +0.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: A bug with Sum (as in Monoid)

Lana Black
In reply to this post by Dannyu NDos
On 06/11/2019 22:19, Dannyu NDos wrote:

> Omg, addition is not even associative? The zeros truly ruined everything.
>
> 2019년 11월 7일 (목) 06:58, Brent Yorgey <[hidden email]>님이 작성:
>
>> How is that worse than the fact that addition is already not associative
>> for floating point types?  At least +0 is really the identity up to (==).
>>
>> On Wed, Nov 6, 2019, 3:49 PM Dannyu NDos <[hidden email]> wrote:
>>
>>> Sum has bug with floating points. Current definition states +0 as the
>>> identity element, while the actual identity is -0 since +0 + -0 = +0.
>>> _______________________________________________
>>> Libraries mailing list
>>> [hidden email]
>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>>
>>
>
>
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
This has little to do with zeroes per se. IEEE 754 addition isn't
associative for any numbers, and examples not involving zeroes aren't
hard to find. Here's one:

Prelude> let a = 1e30 :: Double
Prelude> let b = -1e30 :: Double
Prelude> let c = 1 :: Double
Prelude> a + b + c
1.0
Prelude> a + (b + c)
0.0

There is a good document describing how IEEE754 works, including this
kind of peculiarities:
https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: A bug with Sum (as in Monoid)

Levent Erkok
As pointed out, most "usual" algebraic equations simply do not hold for IEEE754 floating-point numbers. Another example is `1+x == 1 /\ x /= 0` is a satisfiable statement. Just wanted to point out you can use modern SMT solvers to analyze such equalities, and Haskell SBV package (shameless plug) provides a convenient interface. Here's the counter-example showing the non-associativity of addition:


There are other examples in there as well that might be of interest.

Cheers,

-Levent.

On Wed, Nov 6, 2019 at 2:31 PM Lana Black <[hidden email]> wrote:
On 06/11/2019 22:19, Dannyu NDos wrote:
> Omg, addition is not even associative? The zeros truly ruined everything.
>
> 2019년 11월 7일 (목) 06:58, Brent Yorgey <[hidden email]>님이 작성:
>
>> How is that worse than the fact that addition is already not associative
>> for floating point types?  At least +0 is really the identity up to (==).
>>
>> On Wed, Nov 6, 2019, 3:49 PM Dannyu NDos <[hidden email]> wrote:
>>
>>> Sum has bug with floating points. Current definition states +0 as the
>>> identity element, while the actual identity is -0 since +0 + -0 = +0.
>>> _______________________________________________
>>> Libraries mailing list
>>> [hidden email]
>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>>
>>
>
>
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
This has little to do with zeroes per se. IEEE 754 addition isn't
associative for any numbers, and examples not involving zeroes aren't
hard to find. Here's one:

Prelude> let a = 1e30 :: Double
Prelude> let b = -1e30 :: Double
Prelude> let c = 1 :: Double
Prelude> a + b + c
1.0
Prelude> a + (b + c)
0.0

There is a good document describing how IEEE754 works, including this
kind of peculiarities:
https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: A bug with Sum (as in Monoid)

Dannyu NDos
In reply to this post by Brent Yorgey
Imprecise calculation shouldn't be considered as a bug. Topologically speaking, floating point types are regarded as if they had countably infinite precision. So the elements in domain are positive reals, negative reals, the zeros, the infinities, and the NaN.

2019년 11월 7일 (목) 07:29, Brent Yorgey <[hidden email]>님이 작성:
Hint: the problem has nothing to do with zeros.

λ> 0.1 + (0.2 + 0.3) == (0.1 + 0.2) + 0.3
False


On Wed, Nov 6, 2019 at 4:20 PM Dannyu NDos <[hidden email]> wrote:
Omg, addition is not even associative? The zeros truly ruined everything.

2019년 11월 7일 (목) 06:58, Brent Yorgey <[hidden email]>님이 작성:
How is that worse than the fact that addition is already not associative for floating point types?  At least +0 is really the identity up to (==).

On Wed, Nov 6, 2019, 3:49 PM Dannyu NDos <[hidden email]> wrote:
Sum has bug with floating points. Current definition states +0 as the identity element, while the actual identity is -0 since +0 + -0 = +0.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: A bug with Sum (as in Monoid)

Carter Schonwald
Well said, naive summation of numbers with errors built into the geometry / representation of real numbers are def non associative when restricted to bounded / fixed size finite reps! (I like to point out to folks that if you take the log_2 transformation of each half of the real line and then do a uniform grid, then truncate that grid to a finite width interval on each half real line , that roughly gives you the floating point numbers ). 

There’s a few different algorithms you can do for extended / high precision summation, though I don’t think they have the nice associative incremental algorithm we associate (hah!) with the summation and product monoids.  But I would love to be wrong.  Can we use some clever trick to have a higher precision constant space summation alg? Perhaps using eds compensated lib or something else under the covers ?

On Wed, Nov 6, 2019 at 5:41 PM Dannyu NDos <[hidden email]> wrote:
Imprecise calculation shouldn't be considered as a bug. Topologically speaking, floating point types are regarded as if they had countably infinite precision. So the elements in domain are positive reals, negative reals, the zeros, the infinities, and the NaN.

2019년 11월 7일 (목) 07:29, Brent Yorgey <[hidden email]>님이 작성:
Hint: the problem has nothing to do with zeros.

λ> 0.1 + (0.2 + 0.3) == (0.1 + 0.2) + 0.3
False


On Wed, Nov 6, 2019 at 4:20 PM Dannyu NDos <[hidden email]> wrote:
Omg, addition is not even associative? The zeros truly ruined everything.

2019년 11월 7일 (목) 06:58, Brent Yorgey <[hidden email]>님이 작성:
How is that worse than the fact that addition is already not associative for floating point types?  At least +0 is really the identity up to (==).

On Wed, Nov 6, 2019, 3:49 PM Dannyu NDos <[hidden email]> wrote:
Sum has bug with floating points. Current definition states +0 as the identity element, while the actual identity is -0 since +0 + -0 = +0.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries