[Caml-list] truncated division, remainder and arithmetics

[Caml-list] truncated division, remainder and arithmetics

[peio]

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

Re: [Caml-list] truncated division, remainder and arithmetics

[François Bobot]

On 27/01/2016 01:34, peio wrote:
> 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 think it is just because of the assembly instruction available
http://x86.renejeschke.de/html/file_module_x86_id_137.html .

If you are doing computation with big numbers perhaps you can take a look at zarith, which define 
many of the different division convention:

```
external div: t -> t -> t = "ml_z_div" "ml_as_z_div"
(** Integer division. The result is truncated towards zero
     and obeys the rule of signs.
     Raises [Division_by_zero] if the divisor (second argument) is 0.
  *)

external rem: t -> t -> t = "ml_z_rem" "ml_as_z_rem"
(** Integer remainder. Can raise a [Division_by_zero].
     The result of [rem a b] has the sign of [a], and its absolute value is
     strictly smaller than the absolute value of [b].
     The result satisfies the equality [a = b * div a b + rem a b].
  *)

external div_rem: t -> t -> (t * t) = "ml_z_div_rem"
(** Computes both the integer quotient and the remainder.
     [div_rem a b] is equal to [(div a b, rem a b)].
     Raises [Division_by_zero] if [b = 0].
  *)

external cdiv: t -> t -> t = "ml_z_cdiv"
(** Integer division with rounding towards +oo (ceiling).
     Can raise a [Division_by_zero].
  *)

external fdiv: t -> t -> t = "ml_z_fdiv"
(** Integer division with rounding towards -oo (floor).
     Can raise a [Division_by_zero].
  *)

val ediv_rem: t -> t -> (t * t)
(** Euclidean division and remainder.  [ediv_rem a b] returns a pair [(q, r)]
     such that [a = b * q + r] and [0 <= r < |b|].
     Raises [Division_by_zero] if [b = 0].
  *)

val ediv: t -> t -> t
(** Euclidean division. [ediv a b] is equal to [fst (ediv_rem a b)].
     The result satisfies [0 <= a - b * ediv a b < |b|].
     Raises [Division_by_zero] if [b = 0].
  *)

val erem: t -> t -> t
(** Euclidean remainder.  [erem a b] is equal to [snd (ediv_rem a b)].
     The result satisfies [0 <= erem a b < |b|] and
     [a = b * ediv a b + erem a b].  Raises [Division_by_zero] if [b = 0].
  *)
```

Best,

-- 
François

Re: [Caml-list] truncated division, remainder and arithmetics

[Hendrik Boom]

On Wed, Jan 27, 2016 at 01:34:47AM +0100, peio wrote:
> 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.

In the old days when all machines hadn't settled down to one true 
binary arithmetic convention, I noticed that the machines where the 
remainder had the same sign as the dividend were two's complement 
machines, and the ones where the remainder had the same sign as the 
divisor were one's complement machines.

-- hendrik

Re: [Caml-list] truncated division, remainder and arithmetics

[Xavier Leroy]

On 27/01/16 01:34, peio wrote:

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

All contemporary microprocessors that implement division in hardware
implement what you call truncated division.  The other forms of
division and modulus (there are at least two others) can be
implemented on top of that.  See this excellent summary:

Daan Leijen, Division and Modulus for Computer Scientists , July 2003.
http://research.microsoft.com/apps/pubs/default.aspx?id=151917

> 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

Yes, but with the type you propose they would overflow easily for
large enough FP arguments.  In FP computations involving ceil and
floor, it is often possible to do the computation entirely in
floating-point, avoiding catastrophic overflow cases.

> 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).

"truncate" and "int_of_float" are (currently) the same function.

- Xavier Leroy

Re: [Caml-list] truncated division, remainder and arithmetics

[peio]

> All contemporary microprocessors that implement division in hardware
> implement what you call truncated division.  The other forms of
> division and modulus (there are at least two others) can be
> implemented on top of that.  See this excellent summary:
> 
> Daan Leijen, Division and Modulus for Computer Scientists , July
> 2003.
> http://research.microsoft.com/apps/pubs/default.aspx?id=151917

Indeed I missed the fact of the processor available instructions.
Thanks for the clarification and for the reference. Interestingly
Leijen writes about optimisations possible with the euclidean division
which could maybe lead to easier hardware implementation, but this
surely is such a small simplification that instruction sets are
sticking to the truncated one due to inertia of backward-
compatibility..

> If you are doing computation with big numbers perhaps you can take a
> look at zarith, which define 
> many of the different division convention

I didn't knew about zarith and it seems interesting even if this is an
overkill for me.


cheers,
peio