C and Python - Different Behaviour of the Modulo (%) Operation

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

1. Both variants are correct, however in mathematics (number theory in particular), Python's modulo is most commonly used.
2. In C, you do ((n % M) + M) % M to get the same result as in Python. E. g. ((-1 % 10) + 10) % 10. Note, how it still works for positive integers: ((17 % 10) + 10) % 10 == 17 % 10, as well as for both variants of C implementations (positive or negative remainder).

The modulo operation on negative numbers in Python

Unlike C or C++, Python's modulo operator (%) always return a number having the same sign as the denominator (divisor). Your expression yields 3 because

(-5) / 4 = -1.25 --> floor(-1.25) = -2

(-5) % 4 = (-2 × 4 + 3) % 4 = 3.

It is chosen over the C behavior because a nonnegative result is often more useful. An example is to compute week days. If today is Tuesday (day #2), what is the week day N days before? In Python we can compute with

return (2 - N) % 7

but in C, if N ≥ 3, we get a negative number which is an invalid number, and we need to manually fix it up by adding 7:

int result = (2 - N) % 7;
return result < 0 ? result + 7 : result;

(See http://en.wikipedia.org/wiki/Modulo_operator for how the sign of result is determined for different languages.)

Why is the behavior of the modulo operator (%) different between C and Ruby for negative integers?

Wiki says:

Given two positive numbers, a (the dividend) and n (the divisor), a modulo n (abbreviated as a mod n) is the remainder of the Euclidean division of a by n.

.... When either a or n is negative, the naive definition breaks down and programming languages differ in how these values are defined.

---

Now the question is why -40 % 3 is 2 in Ruby or in other words what is the mathematics behind it ?

Let's start with Euclidean division which states that:

Given two integers a and n, with n ≠ 0, there exist unique integers q and r such that a = n*q + r and 0 ≤ r < |n|, where |n| denotes the absolute value of n.

Now note the two definitions of quotient:

1. Donald Knuth described floored division where the quotient is defined by the floor function q=floor(a/n) and the remainder r is:

Here the quotient (q) is always rounded downwards (even if it is already negative) and the remainder (r) has the same sign as the divisor.

2. Some implementation define quotient as:

q = sgn(a)floor(|a| / n) whre sgn is signum function.

and the remainder (r) has the same sign as the dividend(a).

Now everything depends on q:

• If implementation goes with definition 1 and define q as floor(a/n) then the value of 40 % 3 is 1 and -40 % 3 is 2. Which here seems the case for Ruby.
• If implementation goes with definition 2 and define q as sgn(a)floor(|a| / n), then the value of 40 % 3 is 1 and -40 % 3 is -1. Which here seems the case for C and Java.

Python-style integer division & modulus in C

The direction for rounding with signed integer division is not specified in older C standards. However, in C99 it is specified to round towards zero.

Here's portable code which works with all versions of the C standards and CPU architectures:

int py_div(int a, int b)
{
  if (a < 0)
    if (b < 0)
      return -a / -b;
    else
      return -(-a / b) - (-a % b != 0 ? 1 : 0);
  else if (b < 0)
      return -(a / -b) - (a % -b != 0 ? 1 : 0);
    else
      return a / b;
}

int py_mod(int a, int b)
{
  if (a < 0)
    if (b < 0)
      return -(-a % -b);
    else
      return -a % b - (-a % -b != 0 ? 1 : 0);
  else if (b < 0)
      return -(a % -b) + (-a % -b != 0 ? 1 : 0);
    else
      return a % b;
}

I did some superficial tests and it appears to give the same results as Python. This code may not be maximally efficient, but a good C compiler can probably optimize it adequately, especially if you put the code in a header as static functions.

You may also want to take a look at this closely related question: Integer division rounding with negatives in C++.

regarding behaviour of modulo operation?

When we divider (a/b)%MOD , then we do something like this .

(a/b)%MOD

(a*inverse(b))%MOD // You have to find the inverse of b. To find the inverse of b use Fermat Theorem.

Note never divide a/b and then take MOD , first find the inverse of b and then do a*b and then MOD it .

Why -1%26 = -1 in Java and C, and why it is 25 in Python?

Python's %-operator calculates the mathematical remainder, not the modulus. The remainder is by definition a number between 0 and the divisor, it doesn't depend on the sign of the dividend like the modulus.

modulo of a number - python vs c#

The premise of the question is incorrect. The % operator in C# is not the modulus operator, it is the remainder operator, while in Python it is a modulus operator.

As Eric Lippert Describes, modulus and remainder are the same for all positive numbers, but they handle negative numbers differently.

Despite both C# and Python having a % operator, doesn't mean they both represent a modulus.

It's worth noting that other languages, such as C++ and Java use remainder for the % operator, not modulus, which likely contributed to why C# choose to use remainder as well. Since there isn't a lot of consistency in what is meant by the % operator, I would suggest looking it up in the language docs whenever working with a new language.

C Modulo operation differences with negative dividend and divisor is long unsigned

C99 section 6.5.5/6 requires that when a/b is representable:

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

And from 6.5.5/3

The usual arithmetic conversions are performed on the operands.

For more details about arithmetic conversion, please check section 6.3.1.8.

Now it seems on your implementation sizeof(long) = sizeof(long long) = 64 bits

For the first 4 cases, signed or unsigned divisor can be changed to type of numerator (i.e. long long int), but in last 2 cases dividend must be changed(casted or reinterpreted as) to unsigned type as divisor has same width and is unsigned causing the result.

On some systems where sizeof(long) < sizoef(long long), second last result should be different.

---

Related Topics