Built-in mod ('%') vs custom mod function: improve the performance of modulus operation

c++ modular-arithmetic
madMDT picture madMDT · Oct 25, 2015 · Viewed 16.9k times · Source

Recently I came to know that the mod('%') operator is very slow. So I made a function which will work just like a%b. But is it faster than the mod operator?

Here's my function

int mod(int a, int b)
{
    int tmp = a/b;
    return a - (b*tmp);
}

Answer

maddouri picture maddouri · Oct 25, 2015

According to Chandler Carruth's benchmarks at CppCon 2015, the fastest modulo operator (on x86, when compiled with Clang) is:

int fast_mod(const int input, const int ceil) {
    // apply the modulo operator only when needed
    // (i.e. when the input is greater than the ceiling)
    return input >= ceil ? input % ceil : input;
    // NB: the assumption here is that the numbers are positive
}

I suggest that you watch the whole talk, he goes into more details on why this method is faster than just using % unconditionally.

Related questions

Easiest way to convert int to string in C++

What is the easiest way to convert from int to equivalent string in C++. I am aware of two methods. Is there any easier way? (1) int a = 10; char *intStr = itoa(a); string str = string(intStr); (2) int a = 10; stringstream ss; ss &…

Read More
The Definitive C++ Book Guide and List

This question attempts to collect the few pearls among the dozens of bad C++ books that are published every year. Unlike many other programming languages, which are often picked up on the go from tutorials found on the Internet, few …

Read More
How do I iterate over the words of a string?

I'm trying to iterate over the words of a string. The string can be assumed to be composed of words separated by whitespace. Note that I'm not interested in C string functions or that kind of character manipulation/access. Also, …

Read More