Is there a more efficient way to compute positive modulo?

Question

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)?

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. — Sebastian Mach, Apr 10 '14 at 09:26
@user2357112: "That does the wrong thing" : can you elaborate this ? — Jabberwocky, Apr 10 '14 at 09:29
On my environnment : for `i = 10` and `n = 3` `( (i % n) + n ) % n` gives `1`, but for `i = -10` and `n = 3` the result is `2`. Is that supposed to be correct ? — Jabberwocky, Apr 10 '14 at 09:36
@MichaelWalz, yes. `10 = 3 + 3 + 3 + 1`. `-10 = -3 -3 -3 -3 + 2` — FreeNickname, Apr 10 '14 at 09:42
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. — Bruno Ayllon, Apr 10 '14 at 09:50
I had already read through the other post before asking this question , but it didn't have the answer I was looking for. It presented the classical solution, just not the most efficient one. — Bruno Ayllon, Apr 10 '14 at 09:59
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). — rcgldr, Apr 10 '14 at 12:38
*Mathematically*, the modulo `a % b` is defined to be the remainder of the division `a / b`. The common convention in mathematics is for `a / b` to be *euclidean division*, which results in a strictly positive remainder. However, most programming languages, including C and C++, use *truncating division* for `a / b`; the issue isn’t really that modulus is defined incorrectly, rather it’s that a different definition of division is in use, which forces modulus to be defined in the way that it is. — Stephen Canon, Jun 24 '14 at 15:28
@StephenCanon: It really is an incorrect definition, when it doesn't map integers into equivalence classes. — Ben Voigt, Jan 26 '15 at 23:49
@BenVoigt: It's only an incorrect definition if you expect x % n --> y to be the standard mapping from Z into Z/nZ. That's a perfectly nice definition, but it's not the definition of the % operator (which, in fairness, really should be called "remainder" to avoid this confusion). But "modulus" is a heavily overloaded term; there's no point in pretending that it has only one meaning. — Stephen Canon, Jan 27 '15 at 04:47

score 3 · Answer 1 · answered Apr 10 '14 at 09:30

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.

answered Apr 10 '14 at 09:30

pts

80,836
20
110
183

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 – phuclv Apr 10 '14 at 09:45
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. – jcoder Apr 10 '14 at 09:59
2

The logic is equivalent to `return (i % n) + (i < 0) * n;` , assuming `n>0`. – M.M Apr 10 '14 at 10:11
@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). – MSalters Apr 10 '14 at 10:19
It's meant to be a clarification :) These days we trust the compiler to generate the best compiled code for simple arithmetic sequences. – M.M Apr 10 '14 at 10:51

phuclv · Answer 2 · 2019-09-23T08:05:02.270

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;
}

edited Sep 23 '19 at 08:05

answered Apr 10 '14 at 09:56

phuclv

37,963
15
156
475

How will I be bale to know if 2's compliment is used ? – Bruno Ayllon Apr 10 '14 at 09:57
most modern systems use 2's complement – phuclv Apr 10 '14 at 09:59
2

`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. – M.M Apr 10 '14 at 10:15

score 0 · Answer 3 · answered Apr 10 '14 at 09:30

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;

answered Apr 10 '14 at 09:30

Arne Mertz

24,171
3
51
90

Is there a more efficient way to compute positive modulo?

3 Answers3