How does modulus work?

I am not asking asking how the mathematical concept of modulus works, or how `20 % 3 == 2` I understand this fine. I'm more curious how the compiler/interpreter determines this. I can think of a very naive way to do it, like so:

``````int modulus(int a, int b)
{
while (a > b)
{
a -= b;
}
return a;
}
``````

(obviously this needs a few more cases because a can be smaller then b, but you get the idea.) But this would would have some serious performance issues. I threw together some C++ to test the efficiency of both the modulus operator and my naive function.

``````#include <iostream>
#include <chrono>
#include <limits>
#include "chrono_io"
using namespace std;

typedef chrono::high_resolution_clock Clock;

int mod(int a, int b)
{
while (a > b)
{
a -= b;
}
return a;
}

int main()
{
auto start = Clock::now();
cout << 20 % 3 << endl;
auto end = Clock::now();
cout << "Modulus on a small number took "  << end - start << " seconds to calculate.\n";

start = Clock::now();
cout << numeric_limits<int>::max() % 3 << endl;
end = Clock::now();
cout << "Modulus on a large number took "  << end - start << " seconds to calculate.\n";

start = Clock::now();
cout << mod(20, 3) << endl;
end = Clock::now();
cout << "My modulus function on a small number took "  << end - start << " seconds to calculate.\n";

start = Clock::now();
cout << mod(numeric_limits<int>::max(), 3) << endl;
end = Clock::now();
cout << "My modulus function on a large number took "  << end - start << " seconds to calculate.\n";
}
``````

and the output is:

``````2
Modulus on a small number took 43629 nanoseconds seconds to calculate.
1
Modulus on a large number took 5644 nanoseconds seconds to calculate.
2
My modulus function on a small number took 3682 nanoseconds seconds to calculate.
1
My modulus function on a large number took 2153824554 nanoseconds seconds to calculate.
``````

The modulus operator varied from 4,000-70,000 nanoseconds. My function always won on the small numbers, but took around 2 seconds on the large number. Since the modulus operator is so much more consistent, I assume that it compares the number on a bitwise level.

So how does the modulus operator work? I can think of some cases that would be very easy to determine. For example, with mod 2, you can just look at the very last byte. Or with mod 4 you can look at the second to last byte. But not all numbers have such a simple pattern.

• On PCs, this is generally done in hardware (the x86 `DIV` and `IDIV` instructions, which perform integer division, also store the remainder in a register). Are you asking how the hardware does it? May 6, 2015 at 0:17
• Related reading: Assembly Language - How to Do Modulo?
– user22815
May 6, 2015 at 0:20
• Long-division works the same way with binary numbers as it does with decimal. Try it, then think how you might code it (hint: you'll use a lot of shifts). May 6, 2015 at 0:34
• @DJMcMayhem: Yes. Sometimes the compiler has to perform some adjustments to the results in order to be compliant to the language specification for signed arithmetic. In general, the speed of hardware division is good enough that when you do not know the input values at compile-time, it is better to let the hardware do it instead of software emulation. However, if the divisor is known at compile-time, there are tricks that could run faster. See: this and this. May 6, 2015 at 0:58
• Note that the way you are timing things you are really just measuring the time it takes to `cout <<` most of the operations. I doubt you could actually measure the time it takes the processor to do `20 % 3` even if the compiler didn't do it at compile time anyways.
– uesp
May 6, 2015 at 1:25

Nearly all CPUs have a single instruction that will return the modulus of a value. For instance, consider this program:

``````int main()
{
int i = 10;
return i % 3;
}
``````

If I compile this on my Intel OS X machine using g++ -S, the result will be some boilerplate and this:

``````movl    \$3, %eax
movl    \$0, -4(%rbp)
movl    \$10, -8(%rbp)
movl    -8(%rbp), %ecx
movl    %eax, -12(%rbp)         ## 4-byte Spill
movl    %ecx, %eax
cltd
movl    -12(%rbp), %ecx         ## 4-byte Reload
idivl   %ecx
movl    %edx, %eax
``````

The actual modulus happens with this instruction: `idivl %ecx`. When this instruction executes, the quotient will be placed in in `%eax` and the remainder will be placed in in `%edx`.

Since really, this means the `%` operation is only going to take a few clock cycles, the bulk of which is actually moving the data into the right register. Also note that with Intel at least, the same operation finds both the quotient and the remainder, so in reference to your comment, `/` and `%` take exactly the same time. It is the same operation. The only thing that changes is what register the compiler gets the results from.

With any CPU made in the last couple decades, you can assume that any basic mathematical operation (including things that look like library functions like `sqrt` or `cos`) is actually a single machine instruction and generally only take a few clock cycles at most.

[UPDATE]

As people have noted in the comments, to see something approaching a correct timing, you need to remove the output from the timed section like this:

``````int i;
auto start = Clock::now();
i = 20 % 3;
auto end = Clock::now();
cout << i << endl;
``````

But even that is likely not accurate as the actual granularity of the timings may exceed what you are trying to time. Instead, you might want to do this:

``````int i=0;
int x;
auto start = Clock::now();
for(i=0;i<1000000;i++)
x = i % 3;
auto end = Clock::now();
cout << i << endl;
``````

Then divide your timing by 1,000,000. (This will be slightly high as it includes the time taken for an assignment, a comparison and an increment.) On my machine, this gives a time of 5 nanoseconds.

• Really? I was told that sqrt is a very slow instruction. May 6, 2015 at 2:40
• May 6, 2015 at 3:13
• @StevenBurnap that answer is a bit outdated, based on the architecture in year 2011. According to Agner Fog's table, which is updated at least yearly, Haswell SSE2 instructions SQRTSS/SQRTPS (32-bit float, with 23 bits of significance) has a latency of 11 cycles, SQRTSD/SQRTPD (64-bit float) has a latency of 16 cycles. These instructions are the precise ones, i.e. not of the fast approximation variants. It is indeed a lot slower in older architectures. Also keep in mind calling `std::sqrt()` incurs a library call in most C++ compilers. May 6, 2015 at 4:31
• Compilers may additionally apply strength reduction optimization for special cases. For example x % 2 might be optimized to a bit mask if that's faster on a specific architecture. May 6, 2015 at 6:33
• @rwong I would have thought that `std:sqrt` would usually be inlined (and use inline assembly.) But I've never checked. May 6, 2015 at 15:56