11
$\begingroup$

As most of us know, or should know, $-7 \equiv 1 \pmod 4$.

But if you use Java's modulus operator %, you get -3 for the answer, not 1. That's technically correct, but it can cause problems if you're not aware of this as you write a program. C# and Javascript are the same way.

Worse, there are varieties of BASIC which will give you the remainder of the absolute value, e.g., 3 for the example of $-7$; that's clearly wrong.

It looks like only Maple and Mathematica (and by extension, Wolfram Alpha) know better.

Why is this?

$\endgroup$
  • 3
    $\begingroup$ -7 % 4 = -3 can be understood as: keep moving from -7 toward 0 in increments of 4 until you would pass 0 if you did it again. Return what you have at that point. It is a reasonable choice of a representative, all things said. The only problem is that it means that (n%4 : n in Z) has 7 elements when it "should" have 4. By the way, Haskell has separate rem and mod functions, so in a sense it "knows better". $\endgroup$ – Ian Aug 22 '17 at 21:32
  • 2
    $\begingroup$ I suspect it comes from hardware implementations that compute the quotient and remainder in one operation. For positive dividends, the quotient is rounded down, i.e. toward either 0 or $-\infty$. For negative dividends, those are not the same, so which should it be? If you choose to round toward zero, you get a negative remainder. $\endgroup$ – Nate Eldredge Aug 22 '17 at 21:33
  • 2
    $\begingroup$ Some languages, e.g. Pascal, want to keep the fundamental relation (x div y)*y + x mod y = x with $ 0 \le x \bmod y < y$ if $x \ge 0, y>0$. The situation really gets wierd if $y < 0!$ $\endgroup$ – gammatester Aug 22 '17 at 21:37
  • 1
    $\begingroup$ FWIW, in Python the % modulus operator returns a remainder with the same sign as the divisor, and it provides a // floor division operator (i.e., it rounds towards negative infinity). If you like, you can get both quotient & remainder in a single built-in function call: q, r = divmod(n, d); the division & modulus operators / function preserve the identity n = q * d + r. $\endgroup$ – PM 2Ring Aug 22 '17 at 21:40
  • 1
    $\begingroup$ @NateEldredge +1. It's also worth noting that the use of % for remainder is, to the best of my knowledge, inherited from the C language (or rather its predecessor, B) in the early 1970s. Since C is a systems-level programming language, it made a lot of sense for the software specification to follow the hardware. $\endgroup$ – Erick Wong Aug 22 '17 at 22:11
7
$\begingroup$

I believe that the primary justification for this is that division in these languages generally rounds towards 0 instead of towards -infinity when doing integer division (questionably) and they want to preserve the identity that (a // b) * b + (a mod b) = a (rightly). From a mathematical standpoint I completely agree that a mod b should always be in [0, b) and do question the original justification for this decision, however for compatibility it is unreasonable to try and change the standard now. Note that there are other languages beyond the ones you have mentioned, such as Python which do behave in this way.

$\endgroup$
  • 4
    $\begingroup$ This was the opinion of Brian Kernighan: no matter what rounding rule was used, the C language insisted that x = (x%m)+(x/m)*m $\endgroup$ – kimchi lover Aug 22 '17 at 22:08
3
+150
$\begingroup$

Let there be given integers $m \lt 0$ and $b \gt 0$.

Proposition: There exist unique integers $q$ and $r$ satisfying the following conditions:

$\quad q \le 0$

$\quad0 \le -r \lt b\;$ (so $r$ is a nonpositive integer)

$\quad m = qb + r$

The proof is left as an exercise for the interested reader.

If you are working with mixed numbers/improper fractions, this might float your boat; see How to Convert a Negative Mixed Number Into an Improper Fraction : Fractions 101. So $-7/4 = -1 \frac{3}{4}$, and some might insist that $-7 \equiv -3 \pmod 4$ make sense.

$\endgroup$
3
$\begingroup$

Hint: The paper The Euclidean Definition of the Functions $\mathrm{div}$ and $\mathrm{mod}$ by R.T. Boute provides an in-depth discussion of different definitions in mathematics and programming languages.

I'm a great fan of D.E. Knuth and since his F-definition (flooring the quotient and rounding toward negative infinity) is addressed in the paper as one of two preferred approaches, I also recommend reading section 3.4 '$\mathrm{MOD}$' - THE BINARY OPERATION in Concrete Mathematics.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.