Re: [Caml-list] Integer arithmetic: mod

[Edmund GRIMLEY EVANS <edmundo@rano.org>]

I'm responding to some old messages I found in the archive, and I'm
not subscribed, so please forgive the intrusion, but recently I've
been looking at how different languages define integer division and
remainder becaue I had to implement some compiler optimisations
involving those functions.

I strongly advise against leaving the meaning of any built-in or
library function or operator as implementation-defined. If you do this
you will get unportable programs and inefficient programs (because
people who want their programs to be portable will be forced to define
their own versions of the functions).

In my opinion and in most people's opinion, as far as I can tell, if
you're starting afresh, the best way to define integer division is as
rounding downwards. Integer remainder, to be consistent with this, has
the sign of the divisor. There are lots of arguments that support this
type of division, both mathematical and practical, and the only
arguments against it seem to involve compatibility: the other sort of
division is faster on some widely used hardware, is required by some
widely used programming languages and assumed by some existing
software.

A good way to keep everyone happy and make sure people don't get
caught out by their own assumptions is to provide both sorts. If you
do this, the best names to use are DIV and MOD for the good functions
(rounding downwards) and QUOT and REM for the legacy functions
(rounding towards 0). These are exactly the names used in Haskell and
ML and consistent with the names used in Ada, Prolog, Ruby and Scheme.
(I admit I'm not very sure about Prolog. If anyone has a copy of the
ISO standard, please check this for me.)

Here's a little table I made (I hope it doesn't contain too many
errors):

              BAD LEGACY!                     GOOD!
LANGUAGE  Division rounding towards 0     Division rounding downwards
          Remainder has sign of dividend  Remainder has sign of divisor
-----------------------------------------------------------------------
Ada           / rem                           mod
C89           div[quot/rem]
C9x           / % div[quot/rem]
Fortran 90    / MOD                           MODULO
Haskell       quot rem                        div mod
Java          / %
JVM           idiv irem
ML            quot rem                        div mod
Modula-2      div mod
Perl                                          %
Prolog        // rem                          mod
Python                                        / // %
Ruby          remainder                       / modulo divmod
Scheme        quotient remainder              modulo

Edmund

Keywords: negative integer division round truncate quotient remainder
number theory
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr