What's the difference? Remainder vs Modulus

What's the difference? Remainder vs Modulus

Rate This
  • Comments 38

Today, another episode of my ongoing series "What's the difference?" Today, what's the difference between a remainder and a modulus, and which, if either, does the % operator represent in C#?


A powerful idea that you see come up in mathematics and computer programming over and over again is the idea of an equivalence relation.

First off, let's define (again) what a "relation" is; a relation is a function that takes two things, say, integers, and returns a Boolean that says whether the two integers are "related" or not. For example, "is greater than" is a relation. It takes two integers, say 4 and 2, and returns a Boolean that indicates whether 4 "is greater than" 2 or not; in this case, yes, it is.

An "equivalence relation" is a relation which is reflexive, symmetric, and transitive. That is, if ∾ is an equivalence relation, then:

Reflexive: X∾X is true for any X
Symmetric: X∾Y = Y∾X for any X and Y
Transitive: if X∾Y and Y∾Z are both true then X∾Z is also true.

Clearly "is greater than" is not an equivalence relation; though it is transitive, it is neither symmetric nor reflexive. "Have the same sign" on the other hand, is an equivalence relation; all negative numbers are equivalent to each other, all positive numbers are equivalent to each other, and zero is equivalent to itself.

An equivalence relation partitions the set of integers into (possibly infinitely many) equivalence classes. For example, let's consider the equivalence relation A∾B if and only if A-B is evenly divisible by 4. So 0∾4 is true and -86∾2 is true, and so on. We can make four "equivalence classes" where every integer is in exactly one class, and every integer in each class is related to every other integer in that class. The classes are {0, 4, -4, 8, -8, 12, -12, ... }, {1, -3, 5, -7, 9, -11, ... }, {2, -2, 6, -6, 10, -10} and {3, -1, 7, -5, 11, -9, ... }.

These classes are classes of "equivalent" integers, where "equivalence" means "is equally good in terms of determining whether the relation holds". Equivalence classes are often identified by a "canonical" member; in the case of the equivalence classes of "integers that are congruent modulo four", the canonical members are usually taken to be 0, 1, 2 and 3.

One can of course generalize this; given any positive integer n you can create the equivalence relation "A∾B if and only if A-B is evenly divisible by n". This defines n equivalence classes, which are usually identified by the canonical elements 0, 1, ..., n-1. The relation is usually written (somewhat clumsily, in my opinion) as A ≡ B mod n and is read as "A is congruent to B modulo n".

It is very tempting to think of the A % M operator in C# as meaning "partition the integers into M equivalence classes and give me the canonical element associated with the class that contains A" operator. That is, if you say 123 % 4, the answer you get is 3 because 123 ≡ 3 mod 4, and 3 is the "canonical" element associated with the equivalence class that contains 123.

However, that is not at all what the % operator actually does in C#. The % operator is not the canonical modulus operator, it is the remainder operator. The A % B operator actually answer the question "If I divided A by B using integer arithmetic, what would the remainder be?"

In order to work out what the remainder is, we need to first clearly define our terms. The divisor, dividend, remainder and quotient must obey the following identity:

dividend = quotient * divisor + remainder

Now, that is not enough to uniquely determine an answer to the question of what, say, 123 / 4 is. 123 = 30 * 4 + 3 is the desired solution, but 123 = 6000 * 4 - 23877 is also a possible solution. We need to put restrictions on the quotient and remainder.

Naively we might say that the lesser quotient is the better quotient. But of course that does not help either, because 123 = 1 * 4 + 119 is also perfectly good, and 1 is less than 30, but 1 is not a better quotient. We need some better rules; the rules we've come up with to determine the quotient and remainder (assuming that the divisor and dividend are valid, that is, we're not dividing by zero and so on) are:

* If there is any quotient that makes the remainder zero then that's the quotient and the remainder is zero, and we're done.
* Otherwise, do the division in all non-negative integers. Take the largest quotient that keeps the remainder positive.
* If the divisor and dividend have opposite signs then make the quotient negative.
* The remainder can now be worked out so as to obey the identity.

The net result here is that integer division rounds towards zero. That should make sense; we want 123/4 to be 30 with a remainder of 3, not 31 with a remainder of -1. Similarly, we want -123/4 to be -30, not -31! It would be bizarre to say that 4 goes into 123 30 times but goes into -123 -31 times! One expects that changing the sign of a term changes the sign of the result; it does not change the magnitude of the result.

If -123/4 is -30, then what is the remainder? It must obey the identity, so the remainder is -3. That is not the canonical item associated with the equivalence class that contains -123; that canonical item is 1.

It's important to remember this fact when doing things like balancing a hash table:

int bucketIndex = item.GetHashCode() % bucketCount;

or determining if a number is odd:

var oddNumbers = someSequence.Where(x => x % 2 == 1);

The first is wrong because the array index can be negative if the hash code is negative; the second does not classify -123 as an odd number. The % operator does not give the canonical modulus, it gives the remainder.

  • @Dale

    > So?

    Well, if you take care to define reminder, do it properly.

    > Why?

    There's a long list of arguments in e.g. Knuth and Daan's paper which I linked has some good references.

    For one, it makes x%2==1 for all odd x, and hashBucket = hash%numBuckets without casts to unsigned.

  • > Transitive: if X∾Y and Y∾Z are both true then X∾Z is also true; otherwise it is false

    It seems there's an inaccuracy here, namely in the 'otherwise it is false' part. For equivalence there's no difference, but it is not part of 'transitive' definition. Assuming it is correct, we have that !(X∾Y && Y∾Z) -> !X?Z. Contraposition of implication is equivalent transition, so X∾Z -> X∾Y && Y∾Z. So, put simply, we have that if X∾Z is true, then for any Y should also be true X∾Y && Y∾Z which is definitely incorrect for any transitive relation.

    For simple example let's take > relation which is transitive as we know. Let X=3, Y=3, Z=1. 3>3 && 3>1 (X>Y && Y>Z) is not true, so according to your definition 3>1 (X>Z) should be false. Bah.

  • Dale:

    > Alternatively, why is it good to have a system where (-x)/y != -(x/y)?

    Suppose you're implementing a game, simulation or renderer where you have objects positioned in a 2D or 3D space. There is nothing special about the 0 coordinate, and you don't want a discontinuity as objects travel between negative and positive coordinates. Say you measure position in units and split space up into 3 unit square cells. If you use division and round-towards-zero integer division to determine cell, you get a discontinuity as an object moves across zero:

    Position = ... -11, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7...

    Cell = ... -3, -3, -3, -2, -2, -2, -1, -1, -1, 0, 0, 0, 0, 0, 1, 1, 1, 2, 2...

    So your object spends longer in cell 0 and there's a discontinuity between negative and positive space.

    Here's a similar bug where rounding direction errors have caused unintentionally different behaviour in a game for negative coordinate positions than positive ones:

    gaming.stackexchange.com/.../do-positive-coordinate-locations-give-more-ore-in-minecraft

    I'd say it's not that the property "For all x, y: if y!=0 then (-x)/y == -(x/y)" is undesirable, but that in practice it's not as useful a property as "For all x, y, k: if y!=0 then x / y + k ==  (x + ky) / y"

    I would concur with the others and say that in 6 years as a professional programmer and maybe 20 years as an amateur I cannot think of a single instance of wanting the remainder operation, but I can think of a great many instances of wanting the modulus operator. (However, I also don't think I can remember an instance where I cared about the behaviour for a negative *divisor*, so I'm equally happy with floored division or Euclidian division, as described in the Wikipedia article.)

  • As an introductory reference on the subject, your article is missing one detail: an example telling how to get Modulus in C# for those cases where that IS what you want. What is the "best" way to do this? (Assuming you want a formula that works even in corner cases like INT_MIN).

  • public int Modulo (int x, int y)

    {

    if ( y == 0) return 0;

    int reduced = (x / y);

    int absReduced = reduced  < 0 ? -1 * reduced : reduced;

    return absReduced % y;

    }

  • >> Transitive: if X∾Y and Y∾Z are both true then X∾Z is also true; otherwise it is false

    Ivan> It seems there's an inaccuracy here, namely in the 'otherwise it is false' part. For equivalence there's no difference, [...] For simple example let's take > relation which is transitive as we know. Let X=3, Y=3, Z=1. 3>3 && 3>1 (X>Y && Y>Z) is not true, so according to your definition 3>1 (X>Z) should be false. Bah.

    Actually, it fails for equivalences too. Take integer equality, X=1, Y=2, Z=1. X=Y is false, therefore X=Z, 1=1, is false.

    More formally, the author wrote "(X~Y)&&(Y~Z)=(X~Z)" when he only meant to say "(X~Y)&&(Y~Z)->(X~Z)".

    Overall though, well writen. It's interesting to contrast this further with other languages, as Anonymous Coward has. I was under the false impression for some time that C/C++ held to the remainder-quotient identity while rounding toward negative infinity, but this was just an artifact of the compiler/architecture. I have not performed % on a signed number since I learned the truth.

  • An easy way to get the Conical Modulus is to convert to uint. Using Eric's example:

    int bucketIndex = (int)((uint)item.GetHashCode() % (uint)bucketCount);

  • @Aaron: yeah, good catch, thanks. :)

  • @DRBlaise: This doesn't work.  For example, (-1 mod 4) is 3, but your code gives 1.

  • To calculate the modulus "x mod n" I tend to use one of the following methods:

    1) general:  y = x%n; if y<0 { y = y+n; }

    2) when n is a power of 2 use a bit mask:  y = x & (n-1)

    3) in situations I know that x and n are not negative:  y = x%n;  (remainder and modulus are the same in this case)

    And like many other respondents, I also never had any need for the "remainder" operation in my 20+ years of programming (and very frequent need of the modulus). The existing '%' operation cannot be changed in C# anymore, but isn't it time to add a proper modulus operator to the language? For example '%%'.

  • I tend to be really lazy:

    1. int mod = (x % n + n) % n;

    2. int mod = (x + bigConstant) % n;   (if I know that x will never be smaller than -bigConstant, chosen to be a multiple of n)

  • > (Note that if a relation is an equivalence relation then the converse also holds: if X∾Y and Y∾Z are not both true the  X∾Z is false.)

    If X = 1, Y = 2, Z = 1, and the equivalence relation is "=", does this mean that if 1 = 2 and 2 = 1 are not both true (which they aren't), then 1 = 1 is false?

    I think you meant if exactly one of X∾Y and Y∾Z is true, then X∾Z is false. Or I could be missing something.

  • @carlos: Converting to  uint DOES work-Did you run your example through code (-1 mod 4)?

    int x = -1; int y = 4; Console.WriteLine((uint)x % (uint)y);

    This prints 3.

  • "(Note that if a relation is an equivalence relation then the converse also holds: if X∾Y and Y∾Z are not both true the  X∾Z is false.)"

    For example, 1=2 and 2=1 are not both true, so 1=1 is false.

  • @DRBlaise: Sorry, I had a brain fart.  I was thinking (uint) is the same as Abs(), when I know very well it isn't.

    However, your solution still fails unless 2 divides the dividend.  e.g. for -1 mod 5 you get 0.

Page 2 of 3 (38 items) 123