Re: [Caml-list] behaviour of mod

[Yaron Minsky <yminsky@janestreet.com>]

(And this is all in Core_kernel, the portable subset of Core, actually.)

y

On Tue, Jan 20, 2015 at 4:57 PM, Yaron Minsky <yminsky@janestreet.com> wrote:
> Core has an answer to this too.  Core's Int_intf has two extra
> operations, %, for the traditional modular arithmetic mod operator,
> and /%, for the corresponding division operator.  Here's the comment
> on it.  Note that Int.rem is just the mod operator (but we also have
> Int32.rem, Int64.rem, etc.)
>
>   (** There are two pairs of integer division and remainder functions,
>       [/%] and [%], and [/] and [rem].  They both satisfy the same
>       equation relating the quotient and the remainder:
>
>       {[
>         x = (x /% y) * y + (x % y);
>         x = (x /  y) * y + (rem x y);
>       ]}
>
>       The functions return the same values if [x] and [y] are
>       positive.  They all raise if [y = 0].
>
>       The functions differ if [x < 0] or [y < 0].
>
>       If [y < 0], then [%] and [/%] raise, whereas [/] and [rem] do
>       not.
>
>       [x % y] always returns a value between 0 and [y - 1], even when
>       [x < 0].  On the other hand, [rem x y] returns a negative value
>       if and only if [x < 0]; that value satisfies [abs (rem x y) <=
>       abs y - 1]. *)
>
> On Mon, Jan 19, 2015 at 5:59 AM, Stephen Dolan
> <stephen.dolan@cl.cam.ac.uk> wrote:
>> On Sun, Jan 18, 2015 at 6:48 PM, Hannes Mehnert <hannes@mehnert.org> wrote:
>>> -----BEGIN PGP SIGNED MESSAGE-----
>>> Hash: SHA384
>>>
>>> Hi,
>>>
>>> is the behaviour of modulo arithmetics intentional:
>>>  -5 mod 4 = -1 ?
>>>
>>> While this reflects the C behaviour, my expectation was to always have
>>> a positive result:
>>>  -5 mod 4 = 3
>>>
>>> Any hints?
>>
>> Given OCaml's integer division operator, this is the correct "mod".
>>
>> The important property is:
>>
>>     (x / y) * y + (x mod y) = x
>>
>> In other words, (x mod y) gives the error by which (x / y) * y fails to equal x.
>>
>> There are two reasonable (/, mod) pairs which have this behaviour. The
>> first, which C and OCaml use, is where (x / y) rounds towards zero and
>> (x mod y) has the same sign as x, so -5 / 4 = -1 and -5 mod 4 = -1.
>> The second is where (x / y) rounds down and (x mod y) has the same
>> sign as y, so -5 / 4 = -2 and -5 mod 4 = 3.
>>
>> Subjectively, I think the first division operator (round-toward-zero,
>> aka truncate) and the second modulo operator are the more natural. The
>> second modulo operator actually implements modular arithmetic, since
>> with it x mod n buckets the integers x into n equivalence classes
>> differing by multiples of n. But using the first (/) and the second
>> mod breaks the remainder property above.
>>
>> Incidentally, Haskell provides both: the first is called (quot, rem)
>> while the second is (div, mod).
>>
>> Stephen
>>
>> --
>> Caml-list mailing list.  Subscription management and archives:
>> https://sympa.inria.fr/sympa/arc/caml-list
>> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
>> Bug reports: http://caml.inria.fr/bin/caml-bugs