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

Question

One of my pet hates of C-derived languages (as a mathematician) is that

(-1) % 8 // comes out as -1, and not 7

fmodf(-1,8) // fails similarly

What's the best solution?

C++ allows the possibility of templates and operator overloading, but both of these are murky waters for me. examples gratefully received.

Answer 1

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>

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", x);

    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

Answer 2

Best solution for mathematician is to use Python.

C++ operator overloading has little to do with it. You can't overload operators for built-in types. What you want is simply a function. Of course you can use C++ templating to implement that function for all relevant types with just 1 piece of code.

The standard C library provides fmod, if I recall the name correctly, for floating point types.

For integers you can define a C++ function template as (off the cuff) ...

#include <stdlib.h>  // abs

template< class IntType >
IntType mod( IntType a, IntType b )
{
    IntType const r = a%b;
    return (r < 0? r + b : r);
}

... and just write mod(a, b) instead of a%b.

Disclaimer: untested code.

Cheers & hth.,

Answer 3

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.

Now why use templates here? I an overload for int's and longs would do.

int mod (int a, int b)
{
   int ret = a % b;
   if(ret < 0)
     ret+=b;
   return ret;
}

and now you can call it like mod(-1,8) and it will appear to be 7.

edit: I found a bug in my code. It won't work if b is negative. So I think this is better:

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

edit2: Reference: C++03 paragraph 5.6 clause 4: < quote > 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.< end quote>

Answer 4

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.

Answer 5

/* Warning: macro mod evaluates its arguments' side effects multiple times. */
#define mod(r,m) (((r) % (m)) + ((r)<0)?(m):0)

... or just get used to getting any representative for the equivalence class.

Answer 6

Oh, I hate % design for this too....

You may convert dividend to unsigned in a way like:

unsigned int offset = (-INT_MIN) - (-INT_MIN)%divider

result = (offset + dividend) % divider

where offset is closest to (-INT_MIN) multiple of module, so adding and subtracting it will not change modulo. Note that it have unsigned type and result will be integer. Unfortunately it cannot correctly convert values INT_MIN...(-offset-1) as they cause arifmetic overflow. But this method have advandage of only single additional arithmetic per operation (and no conditionals) when working with constant divider, so it is usable in DSP-like applications.

There's special case, where divider is 2^N (integer power of two), for which modulo can be calculated using simple arithmetic and bitwise logic as

dividend&(divider-1)

for example

x mod 2 = x & 1
x mod 4 = x & 3
x mod 8 = x & 7
x mod 16 = x & 15

More common and less tricky way is to get modulo using this function (works only with positive divider):

int mod(int x, int y) {
    int r = x%y;
    return r<0?r+y:r;
}

This just correct result if it is negative.

Also you may trick:

(p%q + q)%q

It is very short but use two %-s which are commonly slow.