The Lumber Room

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

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

with one comment

[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

One Response

Subscribe to comments with RSS.

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

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s