What are the rules for modular arithmetic in C?

Question

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?

Answer 1

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