Euclidean (floored) modulo (mod, %) operator for C, C++

Once again, I was gotcha-ed by the sign of the mod operator in C++. I did -1%n, hoping to get n-1 but instead got -1.
Here’s a little C/C++ function (you could even macro/inline it) to give the “true” (Euclidean) modulo:


static int mod(int a, int base){    
  return ((a % base) + base) % base;
}

Update: So the above runs about twice as slow as just issuing % once, which is to be expected since % is called twice (guess + is pretty cheap in comparison). If half the time a will be positive and half the time negative then a average speed up of 1.5x over the above code can be achieved with the following:


static int mod(int a, int base){    
  return (a < 0 ? ((a % base) + base) % base : a % base);
}

But it is still slower if you already know for sure that a is not negative.

Update: It's worth noting, as it was noted in the comments, that what I describe above is only correct if the base is positive. If the base is negative than euclidean modulo allows a negative result and must be defined accordingly.

Tags: , , ,

4 Responses to “Euclidean (floored) modulo (mod, %) operator for C, C++”

  1. Daniel White says:

    Little info on the web regarding modulo, but you’re right, I much prefer the type you’ve outlined compared to the common ‘Truncated Modulo’.

    It isn’t completely the Euclidean modulo you’ve outlined though as negative bases with Euclidean modulo should actually produce positive results.

    The first one you have is “Floored modulo” which is an improvement on the more common “truncated modulo”. The second one you have is closer to Euclid’s, but there are some errors. Here are some results you can test against. They were obtained from:
    http://research.microsoft.com/en-us/um/people/daan/download/papers/divmodnote.pdf

    // Truncated modulo:
    tmod(8,3) =2
    tmod(8, – 3) = 2
    tmod( – 8,3) = -2
    tmod( – 8, – 3) = -2
    tmod(1,2) = 1
    tmod(1, – 2) = 1
    tmod( – 1,2) = -1
    tmod( – 1, – 2) = -1

    // Floored modulo:
    fmod(8,3) = 2
    fmod(8, – 3) = -1
    fmod( – 8,3) = 1
    fmod( – 8, – 3) = -2
    fmod(1,2) = 1
    fmod(1, – 2) = -1
    fmod( – 1,2) = 1
    fmod( – 1, – 2) = -1

    // Euclidean modulo (see above URL for implementation of this *really* true Euclidean modulo, though speed may be an issue ):
    emod(8,3) = 2
    emod(8, – 3) = 2
    emod( – 8,3) = 1
    emod( – 8, – 3) = 1
    emod(1,2) = 1
    emod(1, – 2) = 1
    emod( – 1,2) = 1
    emod( – 1, – 2) = 1

  2. Demur Rumed says:

    The second %base is because you would get twice the result if you simply added base on positive results. As a result, the ternary expression can be simplified to be faster than your original: return (a < 0 ? (a % base) + base : a % base);

    To explain graphically: http://upload.wikimedia.org/wikipedia/en/2/22/Divmod.svg C follows the top graph. All you want to do is vertically offset the negative result by a constant. This is always within the range of [0..base) which means x%base == x

  3. nick says:

    Thanks man you saved my school project :)

  4. grrrwaaa says:

    @Demur, I couldn’t replicate; with your method mod(-3, 3) gives me 3 rather than 0. But to avoid the double modulo, this does the trick:

    int mod(int a, int base) {
    return (a < 0) ? (base-1 + ((a+1) % base)) : (a % base);
    }

    (Of course it still assumes that base > 0.)

Leave a Reply