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.

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.

View more solutions

Comments

[Armen Tsirunyan]

your code seems to have the same bug as mine had before my edit. What if b is negative? :)

[P i]

I just tested the first chunk and that works, though I can't get my head around why! I would hesitate to use it, as I'm not sure whether it would work for any compiler implementation of % that satisfies the criterion of (x / y) * y + ( x % y) == x. where did you get that from, out of curiosity? Is that in the C standard? If it is robust, it may be preferable over my method (below) for integers in terms of speed.

[Cheers and hth. - Alf]

@Armen: thanks! but I'm too lazy to edit for just that... :-)

[P i]

I am guessing there is a second criterion that |x%y| < |y|. so the specification for x%y would go: x%y (for int x, y) returns an integer r, s.t. (x / y) * y + r == x, and |r| < |y|

[Armen Tsirunyan]

@Ohmu: If you want to cover the second criterion change if to while. But it's practically unnecessary

[Ben Voigt]

@Armen: The second criterion is what makes if work correctly. But your whole premise is dead wrong: Integer division is well-defined in the C++ standard as using truncation toward zero, which guarantees that the sign of x%y is the same as the sign of x

[Ben Voigt]

@Ohmu: Yes, that's in the C++ standard. <quote> For integral operands the / operator yields the algebraic quotient with any fractional part discarded; if the quotient a/b is representable in the type of the result, (a/b)*b + a%b is equal to a.</quote>

[R.. GitHub STOP HELPING ICE]

-1. It's been 11 years since this was implementation defined. ISO 9899:1999 defined it, and unfortunately chose the bad definition.

[R.. GitHub STOP HELPING ICE]

"Get used to getting any representative for the equivalence class"?! That's nonsense. If you wanted that you could just use the original "representative" r. The % operator has nothing to do with equivalence classes. It's the remainder operator and the remainder is well defined algebraically to be nonnegative and less than the divisor. Sadly C defined it the wrong way. Still, +1 for having one of the best answers.

[Armen Tsirunyan]

@Ben, @R.. 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> What will you say to this?

[P i]

Great information Armen! Would you consider editing the knowledge contained in these comments back into your answer when it stabilises? It's a bit hidden here.

[Armen Tsirunyan]

@Ohmu: Good point, hopefully I'll avoid future downvotes... (got 2 already for this answer)

[P i]

You guys are quoting C++ standards. What's the simplest solution guaranteed to run on any C compiler? Armen you need to clarify your solution scope.

[Ben Voigt]

@Armen: You conveniently deleted the footnote <quote>... integer division follows the rules defined in the ISO Fortran standard, ISO/IEC 1539:1991, in which the quotient is always rounded toward zero</quote>. The new C++ standard upgrades this behavior from "preferred" to mandatory, just like Fortran and C.

[Ben Voigt]

@Armen: Also, try explaining the quotient and remainder of (-32768/-1) stored in a 16-bit signed integer type using your quoted specification. The old spec was broken, the new wording is the only one worth anything.

[Armen Tsirunyan]

@Ben: I never saw the footnote, thanks for the info. But let's say the old spec "could be better", and not "was broken" because implementation-defined makes their wording not contradictive... convenient :)

[Ben Voigt]

@Armen: The old spec is broken, but the brokenness is different from the sign issue, and it's easy to miss until you look at the new wording. C++03 didn't have "if the quotient a/b is representable in the type of the result", which causes problems for INT_MIN / -1 (on two's complement implementations). Under the old spec, -32768 % -1 might have to evaluate to -65536 (which also isn't in range of the 16-bit type, yuck!) in order for the identity to hold.

[Hubert Kario]

Doesn't work: for int x=-9001; unsigned int N=2000; it gives 2295, not 999.

[sam hocevar]

@HubertKario Maybe check again? There is no way that something modulo 2000 gives 2295, you must have made a mistake.

[Cheers and hth. - Alf]

re "However whether or not the remainder is negative is implementation-defined.", C++11 guarantees that integer division rounds towards 0.

[Cheers and hth. - Alf]

@ArmenTsirunyan: the r result has to make a = r + b*(a/b) true. no matter how the integer division is implemented the b*something is a multiple of b. this makes r a valid modulo result even if negative. you can add abs(b) to it and it will still be a valid modulo result.

[datenwolf]

@SamHocevar: I think the problem here is the weird C integer promotion rules. signed promote to unsigned and promoting a negative signed integer value to unsigned invokes undefined behavior in C.

[leetNightshade]

This works but defining it as a macro like this is ugly as hell. Here's a templated version: stackoverflow.com/questions/2581594/how-do-i-do-modulus-in-c‌​/…

[Cheers and hth. - Alf]

@downvoters: This answer is still correct, while the selected "solution" now contains incorrect commentary due to new guarantees in C++11. It's pretty darn ironic to downvote an answer that's still correct. With no reason given one has to assume that at least 2 associative persons, with almost absolute degree of ignorance, read this question's commentary and knee-jerk-associatively downvoted. Please do explain your downvotes.

[chux - Reinstate Monica]

Note: corner case problems: 1) mod_rev2(a, INT_MIN) --> infinite recursion. 2) mod_rev2(INT_MIN, some_negative_int) as -INT_MIN may lead to undefined behavior.

[Keith Thompson]

And for a variable whose value might be -99999?

[rcgldr]

The mathematically desired result is for the remainder to be zero or to have the same sign as the divisor (denominator). If the divisor is negative, then the remainder should be zero or negative. The C / C++ implementation results in the remainder being zero or having the same sign as the dividend (numerator).

[Admin]

I corrected an error in the code for b<0 (the previous version computed mod(-a,-b) rather than mod(a,-b)). I'll leave it up to the OP to decide what to do about b == INT_MIN.

[Cheers and hth. - Alf]

@rcgldr: The accepted solution returns non-negative remainder for the case of negative divisor. And so does this answer, because the OP didn't specify a different result in this case, except that this answer produces that result with correct type using a C++ template, which the OP asked for. For the extra requirement, if it is one, one can change r < 0? r + abs( b ) : r to (r == 0? 0 : (r < 0) != (b <0)? r + b : r); it can possibly be simplified, not sure.

[rcgldr]

@Cheersandhth.-Alf - Take a look at wiki modulo. The original release of APL got it wrong, but this was corrected back in the 1960's. Classic languages like Cobol and Fortran and current languages like Matlab and Python have a correct implementation of modulo (some also include a remainder function that works like C / C++).

[Cheers and hth. - Alf]

@rcgldr: However I'm not sure that Fortran has the math semantics, because C++ got the current (post C++11) rounding rule, rounding towards 0, from Fortran.

[rcgldr]

@Cheersandhth.-Alf - For Fortran, modulo() is different than mod(). Look at the wiki article again. I don't know why C++ chose to use mod() instead of modulo(). I'll delete this comment later

[Chris Nolet]

I believe a much simpler (and more efficient) form would be: (x < 0) ? (x % N + N) : (x % N).

[Jive Dadson]

The expression a % b is undefined when b is not positive. It should be treated like division by zero.

[Nisse Engström]

The C11 standard (or the final public draft to be exact) mentions "modulo" six times, but only in relation to the representation of various types. Not once does it mention "modulo" in relation to the remainder operator (%).

[ceztko]

The old declared wrong answer distracts reading. High quality answers just shows the correct answer, don't append it in edits leaving rotten bits. I will upvote when the answer will be cleaned.

[ceztko]

The deregistered user @user1084944 changed the code to calculate mod(a,-b) in case of b negative without proper explanation. I restored the previous version.

[ceztko]

About the change from @user1084944, I thought more about it: 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. Let's take for example: mod(13, -8). If it's mod(a, -b) -> 5, 13 - 5 = 8 -> 8/-8 = -1. But -1 is the ceiling of 13.0 / -8. If it's mod(-a, -b) -> 3, 13 - 3 = 10 -> 10 / -8 it's rational so it can't be. If we take -mod(-a, -b) -> -3, 13 -(-3) = 16 -> 16 / -8 = -2 and -2 is exactly the floor of 13.0 / -8 . I am changing the code accordingly.

[ceztko]

Not a proof of correctness but also searching !google "13 mod -8" and the result is -3.

[cmaster - reinstate monica]

Unfortunately, this does not work with integers. They would need to be converted to floating point before the division to allow you to use floor(). Also, you may loose precision when you convert to float: Try (float)1000000001/3, you'll be surprised at the results!

[Ben Voigt]

assert(signum(rT) == signum(D)); can definitely fail. Correct statement: signum(rT) is a member of the set { 0, signum(D) }, or as an assert assert(rT == 0 || signum(rT) == signum(D));

[TemplateRex]

@BenVoigt can you give a counterexample that would fire the assert?

[Ben Voigt]

Counterexample: D = 10 and d = 5

[Ben Voigt]

Final bold statement in your answer is also wrong, should be "non-negative" rather than "positive"

[TemplateRex]

@BenVoigt thank you for your suggested edits, I updated the answer. BTW, I wrote this answer using a home-grown library, which already incorporated your suggested edits, but which I forgot to add to this answer. See github.com/rhalbersma/xstd/blob/master/include/xstd/cstdlib.‌​hpp

[Admin]

Personally, I think this is a good answer. For example, if you only need to handle -1, you could add the modulus once.

[Kingsley]

This works well, I was looking for a replacement for ill-advised usages of fmod() with negative a parameters.