Arithmetic overflow in rem and mod
According to the documentation, rem and mod must satisfy the following laws: -- > (x `quot` y)*y + (x `rem` y) == x rem -- > (x `div` y)*y + (x `mod` y) == x mod https://hackage.haskell.org/package/base-4.8.0.0/docs/src/GHC-Real.html Note, however, that there is a case when quot and div result in an arithmetic overflow: Prelude> (minBound :: Int) `quot` (-1) *** Exception: arithmetic overflow Prelude> (minBound :: Int) `div` (-1) *** Exception: arithmetic overflow while rem and mod don't: Prelude> (minBound :: Int) `rem` (-1) 0 Prelude> (minBound :: Int) `mod` (-1) 0 Is this a mistake? For the record, I'm aware of the safeint package, which raises the error for rem and mod, and this ticket: https://ghc.haskell.org/trac/ghc/ticket/8695
I think this is a mistake, yes. They should not raise such exceptions, but
rather just wrap around—minBound `quot` (-1) should be -minBound=minBound.
That would justify the behavior of rem and mod, and makes much more sense
than the current behavior for Int as a ring.
On Jun 1, 2015 12:41 PM, "Nikita Karetnikov"
According to the documentation, rem and mod must satisfy the following laws:
-- > (x `quot` y)*y + (x `rem` y) == x rem
-- > (x `div` y)*y + (x `mod` y) == x mod
https://hackage.haskell.org/package/base-4.8.0.0/docs/src/GHC-Real.html
Note, however, that there is a case when quot and div result in an arithmetic overflow:
Prelude> (minBound :: Int) `quot` (-1) *** Exception: arithmetic overflow Prelude> (minBound :: Int) `div` (-1) *** Exception: arithmetic overflow
while rem and mod don't:
Prelude> (minBound :: Int) `rem` (-1) 0 Prelude> (minBound :: Int) `mod` (-1) 0
Is this a mistake?
For the record, I'm aware of the safeint package, which raises the error for rem and mod, and this ticket:
https://ghc.haskell.org/trac/ghc/ticket/8695 _______________________________________________ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/glasgow-haskell-users
The current behavior is quite intentional.
On Mon, Jun 1, 2015 at 1:23 PM, David Feuer
I think this is a mistake, yes. They should not raise such exceptions, but rather just wrap around—minBound `quot` (-1) should be -minBound=minBound. That would justify the behavior of rem and mod, and makes much more sense than the current behavior for Int as a ring.
Well, div has no relation to any ring operation of Int at all. It relies on
a particular choice of representatives for the equivalence classes that the
members of Int-as-a-ring are, and the ring operations do not depend on the
choice of representatives. For example Int and Word are isomorphic as
rings, but have different div operations when identified under this
isomorphism.
On Jun 1, 2015 12:41 PM, "Nikita Karetnikov"
According to the documentation, rem and mod must satisfy the following laws:
-- > (x `quot` y)*y + (x `rem` y) == x rem
-- > (x `div` y)*y + (x `mod` y) == x mod
The real law that defines the behavior of `div` on Int, though, is (the uglier to write in Haskell) toInteger (x `div` y) * toInteger y + toInteger (x `mod` y) == toInteger x together with the conditions that x `mod` y has the same sign as y and |x `mod` y| < |y| (here again |n| = abs (toInteger n)). With the condition that (x `div` y) * y + (x `mod` y) == x interpreted only as an equality of Ints, that is, as an equality mod (say) 2^64, there's no reason why we couldn't have for example 1 `mod` 3 = 0, 1 `div` 3 = 12297829382473034411 -- (2*2^64+1)/3 so the equality of Integers is really needed. When x = minBound :: Int and y = -1, the integers that would satisfy the div/mod law are -x and 0. I'm not sure whether you are intending to suggest that x `div` y be defined (as minBound :: Int), or that x `mod` y raise an exception. But given we should have toInteger (x `div` y) = -toInteger (minBound :: Int), toInteger (x `mod` y) = 0, setting x `div` y = _|_, x `mod` y = 0 is the most sensible definition. If the objection is that since x `div` y is _|_, then so too should be x `mod` y, because of the law (x `div` y)*y + (x `mod` y) == x, I don't think that follows. After all the law is already violated as written when y = 0 since x `div` 0 and x `mod` 0 are both _|_, so the equation takes the form _|_ + _|_ == x. I don't think it is a worse violation of the law to have _|_ + 0 == x when x = minBound and y = -1. Regards, Reid Barton
We went round and round on this back in August.
The ultimate decision was to leave the existing behavior for quot and div
as sufficient consensus for changing it was not reached.
I've updated the ticket in question to reflect that resolution.
-Edward
On Mon, Jun 1, 2015 at 6:40 PM, Nikita Karetnikov
According to the documentation, rem and mod must satisfy the following laws:
-- > (x `quot` y)*y + (x `rem` y) == x rem
-- > (x `div` y)*y + (x `mod` y) == x mod
https://hackage.haskell.org/package/base-4.8.0.0/docs/src/GHC-Real.html
Note, however, that there is a case when quot and div result in an arithmetic overflow:
Prelude> (minBound :: Int) `quot` (-1) *** Exception: arithmetic overflow Prelude> (minBound :: Int) `div` (-1) *** Exception: arithmetic overflow
while rem and mod don't:
Prelude> (minBound :: Int) `rem` (-1) 0 Prelude> (minBound :: Int) `mod` (-1) 0
Is this a mistake?
For the record, I'm aware of the safeint package, which raises the error for rem and mod, and this ticket:
https://ghc.haskell.org/trac/ghc/ticket/8695 _______________________________________________ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/glasgow-haskell-users
participants (4)
-
David Feuer -
Edward Kmett -
Nikita Karetnikov -
Reid Barton