[Caml-list] truncated division, remainder and arithmetics

[peio <peio.borthelle@gmail.com>]

Good evening,


while doing some modular arithmetic I discovered that OCaml uses the
'truncated division' convention for the `/` (quotient) operator.
Actually this convention may seem innocent but it greatly affects the
`mod` (remainder) operator: the sign of the result is the same as
dividend.

After some research I realized that lots of people (D.Knuth!)
criticized this convention in favor of floored division (sign of
remainder same as divisor) or euclidean division (remainder always
positive). I know such a key component of the language isn't likely to
be changed but I would like to get some of the rationals behind this
decision.


I can't think of any case in which the current behavior more natural
but there are clearly situation giving weird results: I encountered one
while multiplying big numbers modulo 2**62 (on 64-bit machine): as
`max_int` is 2**62 - 1 the product could overflow and become negative.
Consequently one can't just write `(a * b) mod m` to get the result of
multiplication on the group Z/mZ if a and b are bigger than 2**31.

The workaround I found was to redefine quotient and remainder to follow
floored division convention:
let rem a b = ((a mod b) + b) mod b
let quo
a b = (a - rem a b) / b
Does anyone see a cleaner way to do it?

I don't know anything about division algorithm, but is it actually
easier/faster to implement the truncated division instead of the
floored division? Is there any other reason I missed to choose
truncated division?


At last another thing that (slightly) bugs me: why don't `ceil` and
`floor` have the type `float -> int`? Because the inherent definitions
of these functions talks about integers, not floats (floor(x) is the
biggest integer less than x). Indeed the `int_of_float (ceil x)` is a
very common pattern (according to some very unscientific searching
through github code search). Maybe even more subtle is that `truncate`
has type `float -> int`. In my opinion the type `float -> float` would
be more appropriate here because the truncation operation is about
approximating a real number with a decimal (we already got
`int_of_float` for rough converting).


cheers,
peio