How Does the Modulus Operator Work

How Does Modulus Divison Work

The result of a modulo division is the remainder of an integer division of the given numbers.

That means:

27 / 16 = 1, remainder 11
=> 27 mod 16 = 11

Other examples:

30 / 3 = 10, remainder 0
=> 30 mod 3 = 0

35 / 3 = 11, remainder 2
=> 35 mod 3 = 2

Understanding The Modulus Operator %

(This explanation is only for positive numbers since it depends on the language otherwise)

Definition

The Modulus is the remainder of the euclidean division of one number by another. % is called the modulo operation.

For instance, 9 divided by 4 equals 2 but it remains 1. Here, 9 / 4 = 2 and 9 % 4 = 1.

Euclidean Division

In your example: 5 divided by 7 gives 0 but it remains 5 (5 % 7 == 5).

Calculation

The modulo operation can be calculated using this equation:

a % b = a - floor(a / b) * b

floor(a / b) represents the number of times you can divide a by b
floor(a / b) * b is the amount that was successfully shared entirely
The total (a) minus what was shared equals the remainder of the division

Applied to the last example, this gives:

5 % 7 = 5 - floor(5 / 7) * 7 = 5

Modular Arithmetic

That said, your intuition was that it could be -2 and not 5. Actually, in modular arithmetic, -2 = 5 (mod 7) because it exists k in Z such that 7k - 2 = 5.

You may not have learned modular arithmetic, but you have probably used angles and know that -90° is the same as 270° because it is modulo 360. It's similar, it wraps! So take a circle, and say that its perimeter is 7. Then you read where is 5. And if you try with 10, it should be at 3 because 10 % 7 is 3.

Why does 2 mod 4 = 2?

Mod just means you take the remainder after performing the division. Since 4 goes into 2 zero times, you end up with a remainder of 2.

How to make sense of modulo in c

The modulo operator in C will give the remainder that is left over when one number is divided by another. For example, 23 % 4 will result in 3 since 23 is not evenly divisible by 4, and a remainder of 3 is left over.

If you want to output whether or not a number is divisible by 4, you need to output something other than just the mod result. Essentially, if mod = 0 than you know that one number is divisible by another.

If you want to output whether or not the number is divisible by 4, I would suggest creating a new character that is set to "y" (yes) or "n" (no) depending on the result of the mod operation. Below is one possible implementation to generate a more meaningful output:

#include <stdio.h>
#include <ctype.h>
#include <math.h>

int main()
{
    int my_input[] = {23, 22, 21, 20, 19, 18};
    int n, mod;
    char is_divisible;
    int nbr_items = sizeof(my_input) / sizeof(my_input[0]);

    for (n = 0; n < nbr_items; n++)
    {
        mod = my_input[n] % 4;
        is_divisible = (mod == 0) ? 'y' : 'n';
        printf("%d modulo %d --> %c\n", my_input[n], 4, is_divisible);
    }
}

This will give the following:

23 modulo 4 --> n
22 modulo 4 --> n
21 modulo 4 --> n
20 modulo 4 --> y
19 modulo 4 --> n
18 modulo 4 --> n

Why is modulus operator slow?

The modulus/modulo operation is usually understood as the integer equivalent of the remainder operation - a side effect or counterpart to division.

Except for some degenerate cases (where the divisor is a power of the operating base - i.e. a power of 2 for most number formats) this is just as expensive as integer division!

So the question is really, why is integer division so expensive?

I don't have the time or expertise to analyze this mathematically, so I'm going to appeal to grade school maths:

Consider the number of lines of working out in the notebook (not including the inputs) required for:

Equality: (Boolean operations) essentially none - in computer "big O" terms this is known a O(1)
addition: two, working left to right, one line for the output and one line for the carry. This is an O(N) operation
long multiplication: n*(n+1) + 2: two lines for each of the digit products (one for total, one for carry) plus a final total and carry. So O(N^2) but with a fixed N (32 or 64), and it can be pipelined in silicon to less than that
long division: unknown, depends upon the argument size - it's a recursive descent and some instances descend faster than others (1,000,000 / 500,000 requires less lines than 1,000 / 7). Also each step is essentially a series of multiplications to isolate the closest factors. (Although multiple algorithms exist). Feels like an O(N^3) with variable N

So in simple terms, this should give you a feel for why division and hence modulo is slower: computers still have to do long division in the same stepwise fashion tha you did in grade school.

If this makes no sense to you; you may have been brought up on school math a little more modern than mine (30+ years ago).

The Order/Big O notation used above as O(something) expresses the complexity of a computation in terms of the size of its inputs, and expresses a fact about its execution time. http://en.m.wikipedia.org/wiki/Big_O_notation

O(1) executes in constant (but possibly large) time. O(N) takes as much time as the size of its data-so if the data is 32 bits it takes 32 times the O(1) time of the step to calculate one of its N steps, and O(N^2) takes N times N (N squared) the time of its N steps (or possibly N times MN for some constant M). Etc.

In the above working I have used O(N) rather than O(N^2) for addition since the 32 or 64 bits of the first input are calculated in parallel by the CPU. In a hypothetical 1 bit machine a 32 bit addition operation would be O(32^2) and change. The same order reduction applies to the other operations too.

How does the %(modulus) operator in c works?

Any numeric literal in c or c++ starting with a zero will be interpreted as octal

So your calculation is 8 modulo 10, which is 8