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

26 Jan 2014

      #8695: Arithmetic overflow from (minBound :: Int) `quot` (-1)
------------------------------------------------+--------------------------
        Reporter:  rleslie                      |            Owner:
            Type:  bug                          |           Status:  new
        Priority:  normal                       |        Milestone:
       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:
------------------------------------------------+--------------------------

Comment (by rleslie):

 Replying to [comment:4 carter]:
...
any changes need to have clear meaning!
For example,  why would minBound * (-1) == minBound?
Is this an artifact of twos-complement?
I can’t find anything in the Haskell 2010 Language Report that
 specifically mentions two’s complement representation, however “All
 arithmetic is performed modulo 2ˆn, where `n` is the number of bits in the
 type.” So given a signed integer representation where `maxBound == 2^(n -
 1) - 1` and `minBound == (-maxBound) - 1` as is the case in GHC, under
 modulo arithmetic it mathematically follows that `(-minBound) ==
 minBound`, which is the same as `minBound * (-1) == minBound`.

 {{{
   maxBound  ==    2^(n - 1)  - 1

   minBound  == (-maxBound)         - 1
             == (-(2^(n - 1)  - 1)) - 1
             ==  (-2^(n - 1)) + 1   - 1
             ==  (-2^(n - 1))

 (-minBound) ==  (-((-maxBound) - 1))
             ==       maxBound  + 1
             ==   2^(n - 1) - 1 + 1
             ==   2^(n - 1)
             ==   2^(n - 1) - 2^n      -- (mod 2^n)
             == (-2^(n - 1))
             == minBound
 }}}

 Note that it is already true that `minBound * (-1) == minBound` for all of
 the signed fixed-precision integer types in GHC. The only change I am
 proposing is to also have {{{minBound `quot` (-1) == minBound}}} instead
 of raising an exception (and likewise for `div`).

 Such a change is consistent with the modulo arithmetic behavior and also
 satisfies the class method laws of § 6.4.2 from the Language Report:

 {{{
 (x `quot` y)*y + (x `rem` y) == x
 (x `div`  y)*y + (x `mod` y) == x
 }}}

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