Modulo operation with negative numbers

Question

In a C program I was trying the below operations (Just to check the behavior)

 x = 5 % (-3);
 y = (-5) % (3);
 z = (-5) % (-3); 

printf("%d ,%d ,%d", x, y, z); 

It gave me output as (2, -2 , -2) in gcc. I was expecting a positive result every time. Can a modulus be negative? Can anybody explain this behavior?

Strontia

Possible duplicate of #4003732 – Smother

possible duplicate of Modulo operator with negative values – Cocky

There are two different interpretations of modulus torstencurdt.com/tech/posts/modulo-of-negative-numbers – Hettie

Just a friendly note for people that land here from a search, but isn't paying full attention to the 'C' language tag: The % operator is defined differently in different languages, see en.wikipedia.org/wiki/Modulo#In_programming_languages - there are many definitions, and what C uses is called "Truncated division". (@Hettie There are more than two, unless you are referring to the existence of two different definitions within C specifically, which is correct, C also supports "Rounded division".) – Rifle

C and Python - different behaviour of the modulo (%) operation (duplicate) – Plumlee

Answer 1

C99 requires that when a/b is representable:

(a/b) * b + a%b shall equal a

This makes sense, logically. Right?

Let's see what this leads to:

---

Example A. 5/(-3) is -1

=> (-1) * (-3) + 5%(-3) = 5

This can only happen if 5%(-3) is 2.

---

Example B. (-5)/3 is -1

=> (-1) * 3 + (-5)%3 = -5

This can only happen if (-5)%3 is -2

Bleach

Should the compiler be smart enough and detect that an unsigned modulo another unsigned is always positive? Currently (well, GCC 5.2) the compiler seems to think that "%" returns an "int" in this case, rather than "unsigned" even when both operands are uint32_t or bigger. – Melan

@FrederickNord Do you have an example to show that behavior? – Eugenieeugenio

Understand that what you describe is the usual int(a/b) (truncate) description of mod. But it is also possible that the rule is floor(a/b) (Knuth). In the Knuth case -5/3 is -2 and the mod becomes 1. In short: one module has a sign that follows the dividend sign (truncate), the other module has a sign that follows the divisor sign (Knuth). – Cordate

This is a case of the C standard being exactly not what I want. I have never wanted truncate to zero or negative modulo numbers, but often want the opposite and need to work around C. – Saltsman

I don't understand, why should a + a%b = a "logically"? – Stribling

@Stribling where is that written? – Bleach

@Stribling the a/b in the expression (a/b) * b + a%b above is integer division, so (a/b) * b is not equal to a unless a is divisible by b. – Pape

This just restates the question in terms of the integer value of a negative quotient. If it were defined as floor(a/b), then the equivalence would only work if the result of the % operator were always nonnegative. C instead does integer conversion by rounding toward 0, which is why the equivalence requires % to return negative values in some cases. – Weingarten

Answer 2

The % operator in C is not the modulo operator but the remainder operator.

Modulo and remainder operators differ with respect to negative values.

With a remainder operator, the sign of the result is the same as the sign of the dividend (numerator) while with a modulo operator the sign of the result is the same as the divisor (denominator).

C defines the % operation for a % b as:

  a == (a / b * b) + a % b

with / the integer division with truncation towards 0. That's the truncation that is done towards 0 (and not towards negative inifinity) that defines the % as a remainder operator rather than a modulo operator.

Celebration

Remainder is the result of modulo operation by definition. There should be no such thing as remainder operator because there is no such thing as remainder operation, it's called modulo. – Miaow

@Miaow not in CS. Look at higher level languages like Haskell or Scheme that both define two different operators (remainder and modulo in Scheme, rem and mod in Haskell). These operators specifications differ on these languages on how the division is done: truncation towards 0 or toward negative infinity. By the way the C Standard never calls the % the modulo operator, they just name it the % operator. – Celebration

Not to be confused with the remainder function in C, which implements IEEE remainder with round-towards-nearest semantics in the division – Gonnella

@Miaow The link that you provided specifically makes the distinction between least positive remainder, and least absolute remainder which is obviously not always positive. It gives -2 as the least absolute remainder of 43 / 5 (since 43 = 9 * 5 - 2). The CS definition is yet again different. But it is worth pointing out that just because we learned something when we were 10 years old, there still might be some subtleties. Try round(2.5) in Python, for instance. It's 2, not 3. And that is mathematically correct, to prevent bias in statistical moments. – Menides

Answer 3

Based on the C99 Specification: a == (a / b) * b + a % b

We can write a function to calculate (a % b) == a - (a / b) * b!

int remainder(int a, int b)
{
    return a - (a / b) * b;
}

For modulo operation, we can have the following function (assuming b > 0)

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

My conclusion is that a % b in C is a remainder operation and NOT a modulo operation.

Hellkite

This does not give positive results when b is negative (and in fact for r and b both negative it gives results less than -b). To ensure positive results for all inputs you could use r + abs(b) or to match bs sign you could change the condition to r*b < 0 instead. – Ethnarch

@MartinEnder r + abs(b) is UB when b == INT_MIN. – Eugenieeugenio

Answer 4

I don't think there isn't any need to check if the number is negative.

A simple function to find the positive modulo would be this -

Edit: Assuming N > 0 and N + N - 1 <= INT_MAX

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

This will work for both positive and negative values of x.

Original P.S: also as pointed out by @chux, If your x and N may reach something like INT_MAX-1 and INT_MAX respectively, just replace int with long long int.

And If they are crossing limits of long long as well (i.e. near LLONG_MAX), then you shall handle positive and negative cases separately as described in other answers here.

Subliminal

Note that when N < 0, the result may be negative as in modulo(7, -3) --> -2. Also x % N + N can overflow int math which is undefined behavior. e.g. modulo(INT_MAX - 1,INT_MAX) might result in -3. – Eugenieeugenio

Yes, in that case you may simply use long long int, or handle the negative case separately (at the cost of losing simplicity). – Subliminal

Answer 5

Can a modulus be negative?

% can be negative as it is the remainder operator, the remainder after division, not after Euclidean_division. Since C99 the result may be 0, negative or positive.

 // a % b
 7 %  3 -->  1  
 7 % -3 -->  1  
-7 %  3 --> -1  
-7 % -3 --> -1  

The modulo OP wanted is a classic Euclidean modulo, not %.

I was expecting a positive result every time.

To perform a Euclidean modulo that is well defined whenever a/b is defined, a,b are of any sign and the result is never negative:

int modulo_Euclidean(int a, int b) {
  int m = a % b;
  if (m < 0) {
    // m += (b < 0) ? -b : b; // avoid this form: it is UB when b == INT_MIN
    m = (b < 0) ? m - b : m + b;
  }
  return m;
}

modulo_Euclidean( 7,  3) -->  1  
modulo_Euclidean( 7, -3) -->  1  
modulo_Euclidean(-7,  3) -->  2  
modulo_Euclidean(-7, -3) -->  2   

Eugenieeugenio

Answer 6

The other answers have explained in C99 or later, division of integers involving negative operands always truncate towards zero.

Note that, in C89, whether the result round upward or downward is implementation-defined. Because (a/b) * b + a%b equals a in all standards, the result of % involving negative operands is also implementation-defined in C89.

Berg

Answer 7

According to C99 standard, section 6.5.5 Multiplicative operators, the following is required:

(a / b) * b + a % b = a

Conclusion

The sign of the result of a remainder operation, according to C99, is the same as the dividend's one.

Let's see some examples (dividend / divisor):

When only dividend is negative

(-3 / 2) * 2  +  -3 % 2 = -3

(-3 / 2) * 2 = -2

(-3 % 2) must be -1

When only divisor is negative

(3 / -2) * -2  +  3 % -2 = 3

(3 / -2) * -2 = 2

(3 % -2) must be 1

When both divisor and dividend are negative

(-3 / -2) * -2  +  -3 % -2 = -3

(-3 / -2) * -2 = -2

(-3 % -2) must be -1

---

6.5.5 Multiplicative operators

Syntax

1. multiplicative-expression:
   • cast-expression
   • multiplicative-expression * cast-expression
   • multiplicative-expression / cast-expression
   • multiplicative-expression % cast-expression

Constraints

2. Each of the operands shall have arithmetic type. The operands of the % operator shall have integer type.

Semantics

3. The usual arithmetic conversions are performed on the operands.

4. The result of the binary * operator is the product of the operands.

5. The result of the / operator is the quotient from the division of the first operand by the second; the result of the % operator is the remainder. In both operations, if the value of the second operand is zero, the behavior is undefined.

6. When integers are divided, the result of the / operator is the algebraic quotient with any fractional part discarded [1]. If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a.

[1]: This is often called "truncation toward zero".

Accommodating

Answer 8

The result of Modulo operation depends on the sign of numerator, and thus you're getting -2 for y and z

Here's the reference

http://www.chemie.fu-berlin.de/chemnet/use/info/libc/libc_14.html

Integer Division

This section describes functions for performing integer division. These functions are redundant in the GNU C library, since in GNU C the '/' operator always rounds towards zero. But in other C implementations, '/' may round differently with negative arguments. div and ldiv are useful because they specify how to round the quotient: towards zero. The remainder has the same sign as the numerator.

Township

You are referring to a text about ANSI C. This is a fairly old norm of C. Not sure if the text is correct with regard to ANSI C, but definitely not with regard to C99. In C99 §6.5.5 integer division is defined to always truncate towards zero. – Cruel

Answer 9

In Mathematics, where these conventions stem from, there is no assertion that modulo arithmetic should yield a positive result.

Eg.

1 mod 5 = 1, but it can also equal -4. That is, 1/5 yields a remainder 1 from 0 or -4 from 5. (Both factors of 5)

Similarly, -1 mod 5 = -1, but it can also equal 4. That is, -1/5 yields a remainder -1 from 0 or 4 from -5. (Both factors of 5)

For further reading look into equivalence classes in Mathematics.

Varletry

Equivalence class is a different concept and modulo is defined in a very strict way. Let's say we have two integer numbers a and b, b <> 0. According to the Euclidean division theorem there exists exactly one pair of integers m, r where a = m * b + r and 0 <= r < abs( b ) . The said r is the result of the (mathematical) modulo operation and by definition is non negative. More reading and further links on Wikipedia: en.wikipedia.org/wiki/Euclidean_division – Quantity

That isn't true. 1 mod 5 is always 1. -4 mod 5 might be 1 too, but they are different things. – Seasonseasonable

Answer 10

Modulus operator gives the remainder. Modulus operator in c usually takes the sign of the numerator

1. x = 5 % (-3) - here numerator is positive hence it results in 2
2. y = (-5) % (3) - here numerator is negative hence it results -2
3. z = (-5) % (-3) - here numerator is negative hence it results -2

Also modulus(remainder) operator can only be used with integer type and cannot be used with floating point.

Checkroom

It would be nice if you can back this up with links to external resources. – Angieangil

Answer 11

I believe it's more useful to think of mod as it's defined in abstract arithmetic; not as an operation, but as a whole different class of arithmetic, with different elements, and different operators. That means addition in mod 3 is not the same as the "normal" addition; that is; integer addition.

So when you do:

5 % -3

You are trying to map the integer 5 to an element in the set of mod -3. These are the elements of mod -3:

{ 0, -2, -1 }

So:

0 => 0, 1 => -2, 2 => -1, 3 => 0, 4 => -2, 5 => -1

Say you have to stay up for some reason 30 hours, how many hours will you have left of that day? 30 mod -24.

But what C implements is not mod, it's a remainder. Anyway, the point is that it does make sense to return negatives.

Seasonseasonable

@FelipeC : if you're using the euclidean division approach, then whether you stayed up for 6 hours or 30 hours will still yield -18 (mod -24), which really provides you with no helpful information, since staying up for 6 versus 30 aren't remotely similar to each other. – Cacique

@RAREKpopManifesto in both cases what remains of the day is 18 hours, so yes it provides helpful information. – Seasonseasonable

that's a false equivalence cuz it involves asking a different question altogether - being up 30 hours mean the -18 refers to "how many hours you're short of 2 full days", while being up 6 hours mean -18 is "how many hours you're short of 1 full day". To be asking the same question of "how many hours you're short of 2 full days", the congruent value needs to be -42. The only congruence of your approach is "how many hours it's short of the next midnight after you went to bed" - a totally different question altogether. – Cacique

@RAREKpopManifesto you misunderstand the abstract algebra. There is no 30 in integers modulo -24 (ℤ/-24ℤ). The members of this set are themselves a set, so the mathematical object we are talking about is {54, 30, 6, -18, -42}. 6 and 30 are not just equivalent, they are exactly the same mathematical object. – Seasonseasonable

Answer 12

If N is the modulus (ie the divisor), then

(x + N) % N

will simply return the modulo of x.

In other words, as a function:

const modulo = (x, N) => (x + N) % N

Example:

result = modulo(-3, 12) // 9

Lordsandladies

Answer 13

I was looking for branchless euclidean modulo and this the closest I got:

#include <stdint.h>

int32_t moduloEuclidean(int32_t a, int32_t b)
{
    int32_t const int32_width = 32;
    int32_t const mod = a % b;

    // mod_sign_mask = (mod < 0)? 0b11111111... : 0
    int32_t const mod_sign_mask = mod >> (int32_width - 1);
    // abs_sign_mask = (b < 0)? 0b11111111... : 0
    int32_t const abs_sign_mask = b >> (int32_width - 1);
    // abs_value = (b < 0)? (~b - (-1)) : (b - 0)
    int32_t const abs_value = (abs_sign_mask ^ b) - abs_sign_mask;

    // result = a % b + (a % b < 0? abs(b) : 0)
    return mod + (mod_sign_mask & abs_value);
}

Note that this solution relies on 2's complement arithmetic and will work only on those platforms that support it. I recommend either compiling with -std=c23 or above or with -fwrapv flag supported by both gcc and clang.

There was a concern that moduloEuclidean(x, 0) has undefined behavior, however so does euclidean division.

Gault

Oh, you are right. It's weird it's UB even when we have standardized 2's complement. But even if it wasn't it would still yield incorrect sign value. – Gault

@chux-reinstate-monica, would (0 < (x)) - (x < (0)) work? – Gault

Ok, I realized it's an overflow when b is INT_MIN and it gets multiply by -1 which also it kinda messes with the result. – Gault

Okay, I switched to my own abs calculation that's not UB under 2's complement and masked it out when remainder is positive. – Gault

Minor: in addition to "solution relies on 2's complement ", it also relies on int is 32-bit. C spec has a minimum range implying at least 16-bit. – Eugenieeugenio

TRUE, I made everything int32_t and added a constant to make that more clear. – Gault

Answer 14

It seems the problem is that / is not floor operation.

int mod(int m, float n)
{  
  return m - floor(m/n)*n;
}

Ney

m converts to float before the division and subtraction and large values incur a precision loss. The division itself readily incurs a precision loss. return fmod(m, n) might be a reasonable alternative, yet using floating point for an integer problem is usually best avoided. – Eugenieeugenio