How to code a modulo (%) operator in C/C++/Obj-C that handles negative numbers

Solution 1:

First of all I'd like to note that you cannot even rely on the fact that (-1) % 8 == -1. the only thing you can rely on is that (x / y) * y + ( x % y) == x. However whether or not the remainder is negative is implementation-defined.

Reference: C++03 paragraph 5.6 clause 4:

The binary / operator yields the quotient, and the binary % operator yields the remainder from the division of the first expression by the second. If the second operand of / or % is zero the behavior is undefined; otherwise (a/b)*b + a%b is equal to a. If both operands are nonnegative then the remainder is nonnegative; if not, the sign of the remainder is implementation-defined.

Here it follows a version that handles both negative operands so that the result of the subtraction of the remainder from the divisor can be subtracted from the dividend so it will be floor of the actual division. mod(-1,8) results in 7, while mod(13, -8) is -3.

int mod(int a, int b)
{
   if(b < 0) //you can check for b == 0 separately and do what you want
     return -mod(-a, -b);   
   int ret = a % b;
   if(ret < 0)
     ret+=b;
   return ret;
}

Solution 2:

Here is a C function that handles positive OR negative integer OR fractional values for BOTH OPERANDS

#include <math.h>
float mod(float a, float N) {return a - N*floor(a/N);} //return in range [0, N)

This is surely the most elegant solution from a mathematical standpoint. However, I'm not sure if it is robust in handling integers. Sometimes floating point errors creep in when converting int -> fp -> int.

I am using this code for non-int s, and a separate function for int.

NOTE: need to trap N = 0!

Tester code:

#include <math.h>
#include <stdio.h>

float mod(float a, float N)
{
    float ret = a - N * floor (a / N);

    printf("%f.1 mod %f.1 = %f.1 \n", a, N, ret);

    return ret;
}

int main (char* argc, char** argv)
{
    printf ("fmodf(-10.2, 2.0) = %f.1  == FAIL! \n\n", fmodf(-10.2, 2.0));

    float x;
    x = mod(10.2f, 2.0f);
    x = mod(10.2f, -2.0f);
    x = mod(-10.2f, 2.0f);
    x = mod(-10.2f, -2.0f);

    return 0;
}

(Note: You can compile and run it straight out of CodePad: http://codepad.org/UOgEqAMA)

Output:

fmodf(-10.2, 2.0) = -0.20 == FAIL!

10.2 mod 2.0 = 0.2
10.2 mod -2.0 = -1.8
-10.2 mod 2.0 = 1.8
-10.2 mod -2.0 = -0.2

Solution 3:

I have just noticed that Bjarne Stroustrup labels % as the remainder operator, not the modulo operator.

I would bet that this is its formal name in the ANSI C & C++ specifications, and that abuse of terminology has crept in. Does anyone know this for a fact?

But if this is the case then C's fmodf() function (and probably others) are very misleading. they should be labelled fremf(), etc

Solution 4:

The simplest general function to find the positive modulo would be this- It would work on both positive and negative values of x.

int modulo(int x,int N){
    return (x % N + N) %N;
}

Solution 5:

For integers this is simple. Just do

(((x < 0) ? ((x % N) + N) : x) % N)

where I am supposing that N is positive and representable in the type of x. Your favorite compiler should be able to optimize this out, such that it ends up in just one mod operation in assembler.