What's the difference? Remainder vs Modulus

What's the difference? Remainder vs Modulus

Rate This

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.

• Wow.

After so many years of C#, it's impressive to realize that I was wrong on the behaviour of such a simple operator Oo

• What is the motivation for % to be remainder operator instead of modulus?

Or, in other words, in what situations remainder is more useful?

• almost every instance of 60 in your arithmetic examples should be replaced with 30. 4 * 60 is 240.  :-)

Whoops; that's what I get for editing the example after it was written. (I was originally going to talk about parity, so the multiplicands were twos.) You've got to apply the edits *consistently* it turns out. Thanks for the note. -- Eric

• Nitpick: By the given definition of Reflexiveness (X∾X is true for any X), "Are both greater than zero" would not be an equivalence relation, as it would not hold for any X <= 0.

I'm not a mathematician, so I'm not sure if there is actually a slightly different true definition of reflexiveness, or if this is an incorrect example.  Looking at Wikipedia I believe it's the latter?  en.wikipedia.org/.../Equivalence_relation

But please don't get me wrong - this was a great post, Eric.  :)

• For reference, a short summary of the sign of the remainder in various languages:

1) Both same sign as divisor and same sign as dividend operators:

Ada, Common Lisp, Haskell, Matlab, Prolog and VHDL use ‘mod’ and ‘rem’; Ruby, Standard ML, Euphoria, Fortran, SenseTalk and Scheme use other names.

2) Same sign as dividend:

ActionScript, bc, bash, C99, C#, Clarion, ColdFusion, D, Go, Java, JavaScript, PHP, PowerShell, Torque Game Engine and Verilog use ‘%’. AMPL, AppleScript, Game Maker, Objective Caml, Delphi, SQL99 and most Basics use various capitalisations of ‘Mod’. Occam, Eiffel, PIC Basic Pro, RPG, Progress and Erlang use others.

This is the same as used by the x86 line of processors.

3) Same sign as divisor:

Lua 5, Python, Tcl and Perl use ‘%’. Maple, Clojure, FileMaker, Mathematica, Minitab, Oberon, Turing, old-style Lua, MathCad and PL/I use various capitalisations of ‘Mod’. Smalltalk, R and J use others.

4) Always positive:

Used by ALGOL-68, Pascal, Stata and Scheme R6RS. The last one also has a closest to zero remainder.

5) Implementation defined:

C90 and C++ use ‘%’.

6) Not defined:

ASP and old-style Basic, although I've never come across something that ancient. Even GW-Basic exhibits the same behaviour as modern Basics.

(Loosely based on the ‘modulo operation’ Wikipedia article, one or two web searches and a quick test.)

P.S. It's pretty rude that the blogging software just throws your post away if you edit too long. Fortunately I saved it to the clipboard.

• Some may find this paper, Division and Modulus for Computer Scientists, helpful:

legacy.cs.uu.nl/.../divmodnote.pdf

• @Vlad - there's no good reason for it to be that way except that early hardware where C first ran defined the operation that way. The remainder function on negative numbers is pretty useless and one in practice invariably winds up fixing the result if negative numbers are a possibility. For all the reasons "it's important to remember this fact," it's clearly the wrong decision to make when designing a programming language's semantics.

• @Matt

The reflexive property isn't dependent on just one comparison, but on the comparison of two comparisons. For example, It doesn't matter if a > 0 or b > 0, but that (a > 0) = (b > 0).

Here is a pseudo-implementation (in something that looks a lot like javascript) that might help:

function bothGreaterThanZero(a, b) {

return a > 0 && b > 0;

}

function isReflexive(a, b, func) {

x = func(a, b);

y = func(b, a);

return x === y;

}

var a = -1, b = -5;

var result = isReflexive(a, b, bothGreaterThanZero);

Since first and second are equal, the relation is reflexive.

• @Darren: the PDPs for which C was originally cooked up had a very limited instruction set. Both kinds of remainders were available as common library functions though. Insofar as C#'s % definition is historically inspired, it is more likely due to the influence of the x86 idiv instruction.

Also note that the first major .Net languages were C# and VB.Net which had a C++ and VB heritage. Since C++'s % was implementation defined it may have made sense to choose VB's Mod behaviour.

• DOH! I need a rewind on that example. That is what  I get for posting without running.

function greaterThanZero(num) {

return num > 0;

}

function isReflexive(a, b, func) {

x = func(a);

y = func(b);

return x === y;

}

var a = -1, b = -5;

var result = isReflexive(a, b, greaterThanZero);

• Surely, the first rule on the reminder you want is abs(reminder) < abs(divisor).

> Similarly, we want -123/4 to be -30, not -31!

We actually want it to be -30.75, and if you round that down (which is what you want in most cases), you get -31. This is what you get in languages inspired by math, rather than CPU instruction sets.

For a good treatment of the subject see Daan's classical paper: legacy.cs.uu.nl/.../divmodnote.pdf

Or even Wikipedia: en.wikipedia.org/.../Modulo_operation

• good to know!

for some reason i thought that % operator always yields the canonical number ( a positive number). It turns out I was wrong and negative numbers are possible too.

• @Eugene

> Surely, the first rule on the reminder you want is abs(reminder) < abs(divisor).

So? This requirement is observed by both the canonical modulus operation and by the x86-based remainder operation.

>> Similarly, we want -123/4 to be -30, not -31!

> We actually want it to be -30.75, and if you round that down

> (which is what you want in most cases)

Why? Why is "round toward negative infinity" a more useful operation than "round toward zero"?

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

• This is one of my bugbears.

I don't think I have *EVER* found the remainder operation useful, except as a means to calculate the modulus.  I've had to write a modulus function for pretty much every language I've ever used, and this isn't always entirely straightforward; handling edge cases (like INT_MIN) can be tricky.

Modulus really ought to be a member of the Math class.

• This is an interesting article.  I am like many of the other posters--in 25 years of practical programming, I have never used any language's "remainder" operator for anything other than modulo on positive integers.

Mandatory nitpick:  not all relations are functions, although all functions are relations.   And even more importantly, not all relations are binary.

Page 1 of 3 (38 items) 123