[Caml-list] behaviour of mod

[Caml-list] behaviour of mod

[Hannes Mehnert]

-----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?

hannes
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2

iQIcBAEBCQAGBQJUu//3AAoJELyJZYjffCjuQH0QAL7FTKcguf2mKMVm1wu+jYvv
b5yOBl+X0vMBCNWjpMfYVf1nIfo+z5cNF+1zy1kHaozE2BV10qywzWe+mzq+1VMo
g1knplZbxahdTgf1Ix+BqF+Fk0voFfUTW/l9Zrg07B5wUEOFcFXKNo14eWSatTs0
tVtSAk6fTffz7IPU/QJfvi7euQ5q6e5MVyvoorpjIz2j/OJ0QXw+catlSPXWdyeW
/2TmdeX6WZuiSruEBAvDgDi8Qcp9x/q1abAjdnrZgfmY3+MxNrFZ+7M+QD+mUua6
pgOe2xdb2gRr5/pOqMLxGpfWZ8b695TS31jZj0GJOZ4sgX/Az/eq1wHSyXiGDpWP
dTr/GUPJWNUEWNeqrF88sOPJK4Zjqr19v7NX86wxvwfQGM4qCbEuYvkVQwBOhtgn
/ewgArQNVHyeAH7R8Ze0S5nqVGDRyJwDj3ef4EVvLGLuibs/fI72x4SQ2x2Xfoz7
tgkkb0g1So15iVo1z3FDbTbeJBaZh/0lyqBno7w4FmJkoc4Ool9DarKaBe+SqHqP
ErYMK+bA9P7e+rBqySnB92dsClg17v2lmzGuKd4damcaAJvsscOJXWbLvteQbxo5
eL8TG2sHCdOV5H4dJCpudUzVkA5dYnJUZuSVG/JAyyZWYm/kkQX0obJJo49GMH4h
MvZ9C+veJNgwRY540fqj
=s3KW
-----END PGP SIGNATURE-----

Re: [Caml-list] behaviour of mod

[Gabriel Scherer]

[-- Attachment #1: Type: text/plain, Size: 1925 bytes --]

This is at least documented in the manual (
http://caml.inria.fr/pub/docs/manual-ocaml/libref/Pervasives.html ):
  > Note that x mod y is negative only if x < 0.

I suppose the idea was to make the least surprising choice (assuming people
knew , and also have the behavior coincide with mod_float. (Interestingly,
the IEEE754 norm requires a "remainder" operation that has an even stranger
behavior (modulo is defined from the round-to-nearest division) and I
haven't proposed anywhere.)

On Sun, Jan 18, 2015 at 7: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?
>
> hannes
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v2
>
> iQIcBAEBCQAGBQJUu//3AAoJELyJZYjffCjuQH0QAL7FTKcguf2mKMVm1wu+jYvv
> b5yOBl+X0vMBCNWjpMfYVf1nIfo+z5cNF+1zy1kHaozE2BV10qywzWe+mzq+1VMo
> g1knplZbxahdTgf1Ix+BqF+Fk0voFfUTW/l9Zrg07B5wUEOFcFXKNo14eWSatTs0
> tVtSAk6fTffz7IPU/QJfvi7euQ5q6e5MVyvoorpjIz2j/OJ0QXw+catlSPXWdyeW
> /2TmdeX6WZuiSruEBAvDgDi8Qcp9x/q1abAjdnrZgfmY3+MxNrFZ+7M+QD+mUua6
> pgOe2xdb2gRr5/pOqMLxGpfWZ8b695TS31jZj0GJOZ4sgX/Az/eq1wHSyXiGDpWP
> dTr/GUPJWNUEWNeqrF88sOPJK4Zjqr19v7NX86wxvwfQGM4qCbEuYvkVQwBOhtgn
> /ewgArQNVHyeAH7R8Ze0S5nqVGDRyJwDj3ef4EVvLGLuibs/fI72x4SQ2x2Xfoz7
> tgkkb0g1So15iVo1z3FDbTbeJBaZh/0lyqBno7w4FmJkoc4Ool9DarKaBe+SqHqP
> ErYMK+bA9P7e+rBqySnB92dsClg17v2lmzGuKd4damcaAJvsscOJXWbLvteQbxo5
> eL8TG2sHCdOV5H4dJCpudUzVkA5dYnJUZuSVG/JAyyZWYm/kkQX0obJJo49GMH4h
> MvZ9C+veJNgwRY540fqj
> =s3KW
> -----END PGP SIGNATURE-----
>
> --
> 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
>

[-- Attachment #2: Type: text/html, Size: 2806 bytes --]

Re: [Caml-list] behaviour of mod

[Mr. Herr]

On 18.01.2015 19:48, Hannes Mehnert 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?
As I understand it, there is not one true solution, see 
http://en.wikipedia.org/wiki/Modulo_operation ,
and the different programming languages handle it very differently.

/Str

Re: [Caml-list] behaviour of mod

[Stephen Dolan]

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

Re: [Caml-list] behaviour of mod

[Yaron Minsky]

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

Re: [Caml-list] behaviour of mod

[Yaron Minsky]

(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