C: The Math Behind Negatives and Remainder

Question

This seems to be the #1 thing that is asked when dealing with Remainder/Mod, and I'm kind of hitting a wall with it. I'm teaching myself to program with a textbook and a chuck of C code.

Seeing as I don't really have an instructor to say, "No, no. It actually works like this", I thought I'd try my hand here. I haven't found a conclusive answer to the mathematical part of this, though.

So... I'm under the impression that this is a pretty rare occurrence, but I'd still like to know what it is that happens underneath the shiny compiling. Plus, this textbook would like for me to supply all values that are possible when using negative remainders, per the C89 Standard. Would it be much to ask if someone could check to see if this math is sound?

1) 9%4
9 - (2) * 4 = 1     //this is a value based on x - (x/y) * y
(2) * 4 + (1) = 9     //this is a check based on (x/y) * y + (x%y) = x

2) -9%4
9 - (2) * 4 = 1; 9 - (3) * 4 = -3   //these are the possible values
(2) * 4 + (1) = 9; (3) * 4 + (-3) = 9    //these are the checks

3) 9%-4
Same values as #2?? 

I tried computing with negatives in the expressions, and came up with ridiculous things such as 17 and -33. Are they 1 and -3 for #3 as well??

4) -9%-4
Same as #1??

In algebraic division, negative signs "cancel". Do they do the same here, or is there something else going on?

I think the thing that gets me confused the most is the negatives. The way I learned algebra in school (5-6 years ago), they are "attached" to their numbers. In programming, since they are unary operators, is that not so? Example: When filling in the value for x on #2, x = 9 instead of x = -9.

I sincerely appreciate any help.

Answer 1

Here you need the mathematical definition on remainder.

Given two integer numbers m, d, we say that r is the remainder of the division of m and d if r satisfies two conditions:

• There exists another integer k such that m == k * d + r , and
• 0 <= r < d.

For positive numbers, in C, we have m % d == r and m / d == k, just by following the definition above.

From the definition, it can be obtainded that 3 % 2 == 1 and 3 / 2 == 1.
Other examples:

4 / 3 == 1 and 5 / 3 == 1, in despite of 5.0/3.0 == 1.6666 (which would round to 2.0).

4 % 3 == 1 and 5 % 3 == 2.

You can trust also in the formula r = m - k * d, which in C is written as:

m % d == m - (m / d) * d

However, in the standard C, the integer division follows the rule: round to 0.
Thus, with negative operands C offer different results that the mathematical ones.
We would have:

(-4) / 3 == -1, (-4) % 3 == -1 (in C), but in plain maths: (-4) / 3 = -2, (-4) % 3 = 2.

In plain maths, the remainder is always nonnegative, and less than the abs(d).
In standard C, the remainder always has the sign of the first operand.

 +-----------------------+
 |  m  |  d  |  /  |  %  |
 +-----+-----+-----+-----+
 |  4  |  3  |  1  |  1  |
 +-----+-----+-----+-----+
 | -4  |  3  | -1  | -1  |
 +-----+-----+-----+-----+
 |  4  | -3  | -1  |  1  |
 +-----+-----+-----+-----+
 | -4  | -3  |  1  | -1  |
 +-----------------------+

Remark: This description (in the negative case) is for standard C99/C11 only. You must be carefull with your compiler version, and do some tests.

Answer 2

Like Barmar's linked answer says modulus in a mathematical sense means that numbers are the same class for a ring (my algebra theory is a bit rusty so sorry the terms might be a bit loosely used:)).

So modulus 5 means that you have a ring of size 5. i.e. 0,1,2,3,4 when you add 1 to 4 you are back at zero. so -9,-4,1,6,11,16 are all the same modulo 5 because they are all equivalent. This is actually very important for various algebra theorems but for normal programmers it's pretty much useless.

Basically the standards were unspecified so the modulus returned for negative numbers just has to be one of those equivalent classes of numbers. It's not a remainder. Your best bet in situations like this is to operate on absolute values when doing modulo operators if you want basic integer division. If you are using more advanced techniques (like public key encryption) you'll probably need to brush up on your math a little more.

For now I'd say still with positive ints in this case and have fun programming something interesting.