What is an effective way to get the smallest non-negative remainder modulo n in C?

Question

Is there an efficient way to get the smallest non-negative remainder modulo n, where n is positive, in C?

This is pretty easy, if the number is non-negative, then it's just% n (where a is a non-negative integer).

However, when a is negative, it seems that the behavior on C89 is determined by the implementation (thanks to kennyTM). That is -2% 11 = -2 or 9.

Answer 1

In addition, in C99, behavior is defined as annoying: -2% 11 = -2.

In general (i.e. n % m when m not constant and the range of n unlimited), you probably cannot do better than usual

 res = ((n % m) + m) % m 

It may be interesting to compare this with the following on your platform; one branch can win against an additional module:

 res = n % m; if (res < 0) res += m; 

Answer 2

You can simply check if the result is negative and then act accordingly:

 int mod(int n, int m) { int r = n % m; if (r < 0) return r + m; else return r; } 

Or without if-then-else and as one expression:

 r = ((n % m) + m) % m; 

Answer 3

What about

 if (a > 0) return a % n; if (a < 0) { r = n - (-a % n); if (r == n) return 0; return r; } 

If a <0, then r = -a % n is the value in [0, n) such that k * n + r = -a for some integer k. Then n - r is the value in (0, n], and since -r = a + k * n, we have n - r = a + (k + 1) * n or = (n - r) + (- k - 1) * n. It follows that n - r is the module a, and since it is located in (0, n], it is non-negative.

Finally, you want the result to be in the range [0, n) and not in (0, n]. To do this, we check if r is equal to n, and if so, return 0. (Which of the course module is n equivalent n)

Answer 4

Few processors implement the remainder in hardware, but rather are synthesized from division and multiplication. So this is not a very cumbersome re-implementation from a machine point of view:

 int qm = n / m * m; // a positive or negative multiple of m, rounded up or down if ( qm <= n ) return n - qm; // usual definition of % else return n - qm + m; // most common definition of -%, with adjustment 

Micro-optimization of conditional + can also be useful. It may be faster or slower on your computer, but it will work:

 int rem = n - n / m * m; return rem + m & -( rem < 0 ); 

Total cost: one regular modulo plus one shift to the right (for generation -(rem<0) ), one bitwise and one additional.