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

I was running some code in here. I tried -40 % 3. It gives me the output 2. when I performed the same operation in C, I get:

int i = (-40) % 3
printf("%d", i);

output is

-1

How are both languages performing the modulo operation internally?


Solution 1:

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:

enter image description here

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.

  1. 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.

Solution 2:

In Java and C, the result of the modulo operation has the same sign as the dividend, hence -1 is the result in your example.

In Ruby, it has the same sign as the divisor, so +2 will be the result according to your example.