CODEWITHSUNDEEP
crubymathimplementationmodulo
Aalok
Aalok

Reputation: 325

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?

Upvotes: 4

Views: 2465

Answers (3)

haccks
haccks

Reputation: 106012

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.

Upvotes: 9

user3386109
user3386109

Reputation: 34829

In the ruby implementation, when the numerator is negative and the denominator is positive, the question that the modulo operator answers is, "What is the smallest positive number that when subtracted from the numerator, allows the denominator to divide evenly into the result?"

In all implementations, when the numerator and denominator are both positive, the question being answered is, "What is the smallest positive number that when subtracted from the numerator, allows the denominator to divide evenly into the result?"

So you can see that the ruby implementation is consistently answering the same question, even if the result is non-intuitive at first.

Upvotes: 0

user3706295
user3706295

Reputation: 37

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.

Upvotes: 1

Related Questions