23

In earlier classes, I was taught that n % d = r and to think about it as n = d*q + r, where d is the divisor, q is the quotient, and r is the remainder (noting that the remainder can never be negative).

So for instance, -111 mod 11 is 10, because -111 = -11*-11 + 10 (as opposed to -111 = -11*10 -1, seeing as how that would give us a negative remainder).

However, when printing the results of -111 % 11, -1 is the result and not 10. Why? Isn't this technically wrong?

Grijesh Chauhan
  • 57,103
  • 20
  • 141
  • 208
Theo Chronic
  • 1,623
  • 2
  • 15
  • 16
  • 2
    Ah, the old negative-operand modulus :-) I recall Python getting it right (in the mathematical sense) in all special cases. – Cameron Jul 04 '13 at 03:46
  • 1
    If you want to force C's '%' operator into a modulus that works the way you expected, just do this: `((a % b) + b) % b` – paddy Jul 04 '13 at 04:01
  • 2
    There is a very nice table on the wikipedia page of Modulo Operation that shows how each language has its own modulo implementation: http://en.wikipedia.org/wiki/Modulo_operation – Daan Timmer Jul 04 '13 at 07:14
  • A helpful post to you [How to code a modulo (%) operator in C/C++/Obj-C that handles negative numbers](http://stackoverflow.com/questions/4003232/how-to-code-a-modulo-operator-in-c-c-obj-c-that-handles-negative-numbers) – Grijesh Chauhan Jul 04 '13 at 07:33
  • 1
    Yu Hao's answer should be marked as the answer in my opinion, but it is worth noting that other languages may do it differently. Ada has two separate functions: a remainder function and a modulo function. Python also handles negative numbers differently when's using its modulo operator. –  Jul 04 '13 at 08:42
  • [Related](http://stackoverflow.com/questions/12710801/c-operator-guarantees) – RiaD Jul 04 '13 at 10:04

3 Answers3

21

Short Answer:

The standard guarantee that (a/b)*b + a%b is equal to a.

In C99, the result of division / will truncated toward zero. The result of % operator will be certain, in this case, -1.

In C89, the result of division / can be truncated either way for negative operands. So the result of % operator is machine-dependent as well.

Long Answer:

From C99 6.5.5

5 The result of the / operator is the quotient from the division of the first operand by the second; the result of the % operator is the remainder. In both operations, if the value of the second operand is zero, the behavior is undefined.

6 When integers are divided, the result of the / operator is the algebraic quotient with any fractional part discarded. If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a; otherwise, the behavior of both a/b and a%b is undefined.

And the footnote on the same page to explain how / works, it says:

This is often called ‘‘truncation toward zero’’.

According to this rule, -111 / 11 can only be -10, not 1. Since (a/b)*b + a%b must be equal to a, we have -111 % 11 is -1.

However, K&R Chapter 2.5 gives a different answer:

The direction of truncation for / and the sign of the result for % are machine-dependent for negative operands, as is the action taken on overflow or underflow.

According to this, either -1 or 10 can be a legal result.

The reason is in C89 3.3.5:

When integers are divided and the division is inexact, if both operands are positive the result of the / operator is the largest integer less than the algebraic quotient and the result of the % operator is positive. If either operand is negative, whether the result of the / operator is the largest integer less than the algebraic quotient or the smallest integer greater than the algebraic quotient is implementation-defined, as is the sign of the result of the % operator. If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a .

It turns out to be a change from C89 to C99.

C99 Rationale 6.5.5 provides some historical reasons:

In C89, division of integers involving negative operands could round upward or downward in an implementation-defined manner; the intent was to avoid incurring overhead in run-time code to check for special cases and enforce specific behavior. In Fortran, however, the result will always truncate toward zero, and the overhead seems to be acceptable to the numeric programming community. Therefore, C99 now requires similar behavior, which should facilitate porting of code from Fortran to C. The table in §7.20.6.2 of this document illustrates the required semantics.

And here's the table in §7.20.6.2:

numer denom quot rem
 7      3    2    1
–7      3   –2   –1
 7     –3   –2    1
–7     –3    2   –1
Yu Hao
  • 119,891
  • 44
  • 235
  • 294
  • 1
    I think only -1 is allowable—footnote 90 (in version n1256 of the C99 standard) says, in reference to the text "[...] the algebraic quotient with any fractional part discarded", that "this is often called truncation towards 0". So I take that to mean that `-111 / 11` can only be -10, and therefore `-111 % 11` can only be -1 due to the requirement that `(a/b)*b + a%b` must equal `a`. – Adam Rosenfield Jul 04 '13 at 04:04
  • Additionally, bitwise operators function differently! Even though `&` and `>>` are usually compared to modulo and division in powers of 2, `>>` does not "truncate toward zero", so `-5 >> 1 == -3`, and `-11 & 3 == 1` (while `-11 % 4 == -3`) – i Code 4 Food Jul 04 '13 at 04:26
  • 1
    Yes, this was changed in C99. C89 compilers can do either, and generally do whatever is most convenient for the hardware. – torek Jul 04 '13 at 04:51
  • @iCode4Food Right shift of int is implementation-defined. – Jim Balter Jul 04 '13 at 06:21
6

For modulus, -1 would be a wrong answer.

C's % operator is a remainder operator not a modulus operator though — and for remainder, either 10 or -1 is allowable.

Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
Jerry Coffin
  • 476,176
  • 80
  • 629
  • 1,111
  • 1
    Please define what you mean with modulus. There seem to be different definitions, depending on context, and for some of those, ISTM that -1 would be correct. – Rudy Velthuis Jun 08 '14 at 18:03
  • @RudyVelthuis: "modulus" is normally associated with [modular arithmetic](http://mathworld.wolfram.com/ModularArithmetic.html). At least as modular arithmetic is normally defined, only non-negative numbers are allowed. – Jerry Coffin Jun 08 '14 at 18:10
  • As I said, it depends on the context. If you are hinting at Euclidian division, then indeed, the remainder is always positive. But in other contexts, this is not necessarily the case. Especially since this is a programming forum, it should be known that the meaning of "modulus" can differ from language to language. – Rudy Velthuis Jun 08 '14 at 21:10
  • @RudyVelthuis: I disagree. Modulus means what it means. Most languages implement something that may be similar under some circumstances, but (in most cases) will differ under others. – Jerry Coffin Jun 08 '14 at 22:40
  • Can you give an authorative definition of modulus, then? ISTM that modulus means different things in different contexts. – Rudy Velthuis Jun 09 '14 at 08:37
4

The % operator is implemented such that a == b * (a / b) + (a % b) is true, where we use integer division.

In this case -111 / 11 is -10, so -111 == 11 * -10 + x is satisfied by x == -1.

Zong
  • 6,160
  • 5
  • 32
  • 46