What does precisely the modulo operator do?


An integer n is said to divide another integer a when there is an integer q such that
a = q*n. In other words, nothing remains after the division. For example 2 divides 4. We call n the divisor, a the dividend, and q the quotient. However, 3 does not divide 7 because there is no integer q such that 7 = q*3. The integer 7 contains no more than two 3s and there will be a leftover of 1. This is called the remainder and is denoted by r. From this, we have the following equation:

a = q*n + r where 0 <= |r| < |n|

Most programming languages provide an operator that computes r from a and n. For example, C/C++ provide the % operator. It is sometimes called the modulo operator and sometimes the remainder operator. Unfortunately, different languages implement this operator in different ways. In fact, it also depends on the underlying hardware. So it’s critical to fully understand what kind of modulo operator your programming language is providing.

The problem is that q and r are not unique for all integers a and n. For example, for a = 7 and n = 3 we have:

7 = 2*3 + 1
7 = 3*3 – 2

The first one is an example of floored division where q = floor(a/n) and therefore
r = an * floor(a/n). This is the result that people usually expect. But the second one, which uses the ceiling function instead, is also correct. Things get more complicated when a or n or both are negative integers. For example, for a = -7 and n = 3 we have:

-7 = -2*3 – 1
-7 = -3*3 + 2

Notice that the signs of the quotient and the remainder are not only dependent on the signs of the divisor and the dividend, but also on what kind of division we are performing. Also notice that there are four combinations for the signs of the divisor and dividend.

Three kinds of divisions are most common: Truncated division, floored division, and Euclidean division. Each has different implications on the signs and values of the quotient and the remainder. Let’s discuss them in a bit more depth.

In truncated division, the quotient is computed as trunc(a/n). So if a/n is positive (a and n have the same signs), then it has the same effect as applying the floor function. And if a/n is negative (a and n have different signs), then it has the same effect as applying the ceiling function. Truncation actually always rounds towards zero. By checking the four possible signs of the dividend and divisor, we can prove that the sign of the remainder r has always the same as the dividend a. Examples of languages using this implementation are C99, C11, C++11, all versions of C#, and all versions of Java. The operator in this case is called the remainder operator.

Now that you know about truncated division, you can easily see why this code, which attempts to determine whether an integer n is odd or not, won’t work:

if(n % 2 == 1) { … }
else { …}

If the variable n is always nonnegative then the code will work. But if it is negative then the sign of the remainder will be negative and so the condition will not be able to determine whether n is odd or not. The simplest way to do this is as follows:

if(n % 2 != 0) { … }
else { …}

Here, we are exploiting the property that every integer is either odd or even. An integer is odd if and only if it’s not even.

In floored division, the quotient is always rounded down. That is, q = floor(a/n) and therefore r = an * floor(a/n). By checking the four possible signs of the dividend and divisor, we can prove that the sign of the remainder r has always the same as the divisor n. Examples of languages using this implementation are Perl and Python. The operator in this case is called the modulo operator.

Many programming languages provide both operators such as Fortran, MATLAB, Prolog, Common Lisp, Haskell, Scheme, and Ruby. On the other hand, some other languages have not specified the kind of operator they are providing as part of their standards and so it depends on the particular implementations. C90 and C++98 are examples of such languages.

In Euclidean division, the remainder is always positive or zero, which is very suitable in mathematical studies since it simplifies definitions and proofs. This is computed by using the following rules:

If n > 0 then q = floor(a/n)
If n < 0 then q = ceiling(a/n)

In fact, in mathematics, it is common to restrict the divisor to be positive to simplify calculations concerning quotients and remainders. Few programming languages provide this operator.

This discussion does not only apply to integer division, but also to floating-point division. In that case, the quotient is restricted to be an integer and therefore it is possible to have a remainder. For more information, search for “Modulo Operation” in Wikipedia.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s