Arithmetic overflow in rem and mod
Reid Barton
rwbarton at gmail.com
Tue Jun 2 15:51:22 UTC 2015
The current behavior is quite intentional.
On Mon, Jun 1, 2015 at 1:23 PM, David Feuer <david.feuer at gmail.com> wrote:
> 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" <nikita at karetnikov.org> wrote:
>
>> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/glasgow-haskell-users/attachments/20150602/b01eb3e6/attachment.html>
More information about the Glasgow-haskell-users
mailing list