Efficient way to get the least non-negative residue modulo n in C?

Question

Hi,

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

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

However when a is negative, it appears the behaviour, in C89, is implementation defined (thanks kennyTM). I.e. -2 % 11 = -2 or 9.

Thanks.

Answer 1

Something like this should do:

if(value<0)
    mod = n-(-value)%n;
else
    mod = value%n;
if(mod>=n)
    mod -= n;

The worst code path is 6 basic instructions (compare, negation, modulus, subtraction, compare, subtraction). As Potatoswatter commented, all the extra instructions are significantly cheaper than the modulus itself.

Depending on how your compiler works, it may be interesting to invert the condition for the first if and swap the statements to have more even costs across cases.

Also, as sth pointed out, you will be getting an overflow when value is equal to the minimum value for int. If your code has to work with unconstrained inputs, you may add a check to add n to the value when you hit this edge case, at the beginning of the code. This adds +2 base instructions to the code (check + either add or jump).

Unless you can rely on how the target machine will deal with negative modules, you can't get more efficiency than this. Note that, while C99 defines how to deal with negative modules, this doesn't guarantee that the machine's module instruction works that way (that's probably a winning bet for most cases, but still a bet): if it works differently, it's the compiler's task to tweak the result to be what the language specification requires it to be (which means additional machine code generated by the compiler to check and adjust the result).

Unlike most other answers provided, my approach does the checks and manipulations for negative values before computing the modulus, so it is always computed on non-negative values. I tried to give you architecture-agnostic code. If you can be sure that the CPU computes negative modules as C99 defines, then feel free to rely on that fact to simplify the code and shave a few cycles off.

Hope this helps.

Answer 2

You could 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 a single expression:

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

Answer 3

I don't know how efficient this is, but you could try:

result = (number + (number % modulus)) % modulus

Answer 4

Furthermore, in C99 the behaviour is defined to be the annoying one: -2 % 11 = -2.

In general (i.e., n % m when m is not constant and the range of n is unconstrained), you probably can't do better than the usual

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

It may be interesting to compare that to the following on your platform; one branch might win against the extra modulo:

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

Answer 5

How 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 a value in [0, n) such that k * n + r = -a for some integer k. Then n - r is a value in (0, n], and since -r = a + k * n, we have n - r = a + (k + 1) * n, or a = (n - r) + (-k - 1) * n. From this you can see that n - r is the modulus of a, and since it is in (0, n], it is non-negative.

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

Answer 6

Few processors implement remainder in hardware, rather it's synthesized from a division and a multiplication. So this is not really a cumbersome reimplementation from the machine's standpoint:

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 the conditional + may also be beneficial. This could be faster or slower on your machine, but it will work:

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

Total cost: one regular modulo plus one right-shift (to generate -(rem<0)), one bitwise and, and one add.