The “most natural” definition of the div and mod functions

"Consign them to dust and damp by way of preserving them"

The “most natural” definition of the div and mod functions

[incomplete: must add examples and more discussion]

Most programming languages include a “remainder” or “modulo” function, and also an integer division (“quotient”) function. Given two integers $D$ and $d$ , let’s call the results of these functions $r$ and $q$ respectively.

For positive $D$ and $d$ , it is clear what $q$ and $r$ should be: $q = \left\lfloor D/d \right\rfloor$ is the largest integer $n$ such that $nd \le D$ , and $r = D - qd$ is the remainder which therefore satisfies $0 \le r < d$ .

What should we do when, as frequently happens, $D$ is negative, or (as less frequently happens) $d$ is negative?

For negative $D$ and positive $d$ , there are two choices when $D$ lies between two multiples of $d$ (i.e. $q_1 d < D < q_2 d$ ):

(1) Set $q$ to the lesser value, so that $0 \le r < d$ continues to hold, or
(2) Set $q$ to the greater (and therefore smaller in magnitude) value.

There are very good reasons why (1) is preferable to (2): it ensures that the function $a \bmod m$ is always positive no matter what the value of $a$ , so that, for example, $a \equiv b \pmod m \iff (a \bmod m) = (b \bmod m)$ .

And indeed that is what the more recent programming languages do. There is a table on Wikipedia: C, C++, Java, Go(!), OCaml(!), PHP, all have the “bad” behaviour, while Maple, Mathematica, Microsoft Excel, Perl, Python, Ruby have the “good” behaviour. Some languages have separate functions for both behaviours (e.g. Haskell has quotRem and divMod functions, similarly Common Lisp, Fortran, MATLAB).

There’s also the question of what to do when $d$ is negative, which turns out not to matter much (as long as it’s consistent with the above). One defintion is to continue to have $q$ be the lesser value, and the other is to continue to insist that $r \ge 0$ . Both are fine, though sometimes the latter is nicer.

These are elaborated in The Euclidean Definition of the Functions div and mod by Raymond T. Boute, ACM Transactions on Programming Languages and Systems, Vol 14, No. 2, April 1992.

Written by S

Mon, 2015-01-12 at 09:30:35

Posted in computer science, unfinished

One Response

Subscribe to comments with RSS.

[…] to this blog from my friend Shreevatsa which helped me look up the different ways of finding the remainder and […]

Modulo operator in C | Recursive Complexity

Mon, 2015-01-12 at 22:54:34

Reply

S	M	T	W	T	F	S
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30	31

The Lumber Room