2

Modulo in C and C++ does not behave in a mathematically correct manner, as it returns a negative result when performing the modulo of a negative number. After doing some research, it seems the classic way of implementing a correctly behaving one is:

positive modulo(int i, int n) { return ( ( (i % n) + n ) % n ); }

Considering modulo is computationally expensive, is there a more efficient way to compute positive modulo for any number (I already saw the solution for powers of 2, but I need something generic)?

Improve this question
13
  • 1
    Just abs the value first? Commented Apr 10, 2014 at 9:21
  • @RichardJ.RossIII: That does the wrong thing. Commented Apr 10, 2014 at 9:21
  • 1
    Addition in C and C++ does not behave in a mathematically correct manner, as it returns a negative result when performing the addition of very large numbers. // sorry, couldn't resist. Most operations in programming are not mathematically correct. Commented Apr 10, 2014 at 9:26
  • 2
    The mathematical result of modulo should always be positive, and should be how much you need to add to the number to reach the closest multiple of n for the divisor d. Commented Apr 10, 2014 at 9:50
  • 1
    Mathematical modulo has the same sign as the divisor or zero (rounding towards negative infinity). C / C++ modulo has the same sign as the dividend or zero (rounding towards zero). Commented Apr 10, 2014 at 12:38

3 Answers 3

Reset to default
3

This may be slower or faster, depending on the compiler, the optimization level and the architecture:

static inline int modulo(int i, int n) { const int k = i % n; return k < 0 ? k + n : k; }

The reason why it can be slower is that the condition operation may introduce a branch, and sometimes branches are slow.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

The branch is slow but most devices today that don't have hardware divisor are mostly embedded systems in which branch or not doesn't affect much performance since it doesn't have superscalar or some other features as well
On my system it compiles to movl %edi, %eax cltd idivl %esi addl %edx, %esi movl %edx, %eax testl %edx, %edx cmovs %esi, %eax Which doesn't have a branch, it instead uses a conditional move which should be fast.
The logic is equivalent to return (i % n) + (i < 0) * n; , assuming n>0.
@MattMcNabb: With modern compilers, (i<0) * n no longer is an optimization. On systems where that can be implemented branchless, the equivalent conditional code is also compiled without branches (see jcoder's example).
It's meant to be a clarification :) These days we trust the compiler to generate the best compiled code for simple arithmetic sequences.
1

The solution in pts's answer is probbaly the best solution. It often compiles to a branchless code, but even if there are slowdowns by the branch, it may possibly be faster than the division anyway. But in case you really need to avoid branching

inline int modulo(int i, int n) { int k = i % n; int a = -(k < 0); // assuming 2's complement // or int a = ((k < 0) << (INT_SIZE - 1)) >> (INT_SIZE - 1); if your system doesn't use 2's complement return k + n & a; }
Improve this answer

3 Comments

How will I be bale to know if 2's compliment is used ?
most modern systems use 2's complement
a = -(k < 0); works regardless of representation, it will set a to either 0 or -1. To make the code portable, change n & a to n * -a. Hopefully the compiler will generate optimal code in both cases.
0

The second modulo in your formula is necessary only to substract n again if the modulo was posivite in the first place. So it should be at least as performant to only conditionally add n:

 auto m = (i % n); return (m < 0) ? m+n : m;
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.