Re: [GHC] #8695: Arithmetic overflow from (minBound :: Int) `quot` (-1)

28 Jan 2014

      #8695: Arithmetic overflow from (minBound :: Int) `quot` (-1)
------------------------------------------------+--------------------------
        Reporter:  rleslie                      |            Owner:
            Type:  bug                          |           Status:  patch
        Priority:  normal                       |        Milestone:  7.8.1
       Component:  libraries/haskell2010        |          Version:  7.6.3
      Resolution:                               |         Keywords:
Operating System:  Unknown/Multiple             |     Architecture:
 Type of failure:  Incorrect result at runtime  |  Unknown/Multiple
       Test Case:                               |       Difficulty:
        Blocking:                               |  Unknown
                                                |       Blocked By:
                                                |  Related Tickets:  #1042
------------------------------------------------+--------------------------

Comment (by ekmett):

 rwbarton: I fully expected to get dinged on the fact that Int can't be a
 proper domain. I should have included the caveat that it is 'insofar as it
 can be'.

 That said, when a function can be continuously extended sensibly in only
 one way, I tend to favor extending it.

 Re: `div (toInteger a) (-1) == toInteger c`, here `(-1)` is a even unit of
 `Z mod 2^n`, but we can't even multiply it by all of the ring and pass
 that law.

 The only way to pass your condition without partiality would be to use 1s
 complement to fix the asymmetry between positive and negative values, but
 it of course comes with all sorts of other problems and is a complete non-
 starter.

 That said, the operation can pass a slightly different condition, which is
 that the answers match mod 2^n.

 In other words

 {{{
 c = div a b = fromInteger (div (toInteger a) (toInteger b))
 }}}

 {{{
...
...
...
fromInteger $ toInteger (minBound :: Int) `div` (-1) :: Int
 -9223372036854775808
...
...
...
fromInteger $ toInteger (minBound :: Int) `quot` (-1) :: Int
 -9223372036854775808
 }}}
This extension to `div` and `quot` complies with doing this operation in
 the larger `Integer` domain and coming back down into the restricted
 range, just like `(*)`, `(-)`, `(+)`, etc. do. Those operations also don't
 comply with your desired law.

 carter: There are multiple packages that provide overflow protection. e.g.
 http://hackage.haskell.org/package/safeint

 That said, `Int` explicitly does not.

 2s complement introduces particularly hairy corner cases around
 `minBound`. `-minBound = minBound`, `abs minBound < (0 :: Int)` etc. and
 it is that same counter-intuitive corner case arising here.

--
Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8695#comment:22
GHC http://www.haskell.org/ghc/
The Glasgow Haskell Compiler