4

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?

Mr Lister
  • 45,515
  • 15
  • 108
  • 150
Aalok
  • 325
  • 5
  • 14
  • http://www.yourdailygeekery.com/2011/06/28/modulo-of-negative-numbers.html – Jens Wirth Jun 06 '14 at 05:41
  • Another duplicate: http://stackoverflow.com/questions/4003232/how-to-code-a-modulo-operator-in-c-c-obj-c-that-handles-negative-numbers – alk Jun 06 '14 at 05:41
  • 1
    The currently linked question is not a duplicate. That one is about `(int) % (unsigned int)`, which has nothing to do with this question. Now http://stackoverflow.com/questions/828092/python-style-integer-division-modulus-in-c would be much better suited as a duplicate. – Mr Lister Jun 06 '14 at 05:46
  • @MrLister; That's also not matches as a better dupe actually. – haccks Jun 06 '14 at 06:12
  • 1
    @haccks Why did you capitalize c to C in the second to last line but not in the second line? Your other edits brought the question back to elementary school level. If you want to edit other people's question, you should do that after you have studied English enough. – sawa Jun 06 '14 at 10:40
  • Dis agree with close vote. Question is very clear. – haccks Jun 06 '14 at 18:15

3 Answers3

9

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.
Mike 'Pomax' Kamermans
  • 49,297
  • 16
  • 112
  • 153
haccks
  • 104,019
  • 25
  • 176
  • 264
1

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.

user3706295
  • 37
  • 3
  • *In Java and C, the result of the modulo operation has the same sign as the dividend,*: Not guaranteed in in C89. – haccks Jun 06 '14 at 06:15
  • first of all i want to know why result is +2 in ruby?? – Aalok Jun 06 '14 at 06:18
  • 1
    @Aalok, in Ruby, it has the same sign as the divisor (+ here), so it will calculate like -3*14 = -42 +2 = -40. But for C it will calculate like -3*13=-39 -1= -40. so +2 and -1 are the remainder of each case. – user3706295 Jun 06 '14 at 07:01
0

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.

user3386109
  • 34,287
  • 7
  • 49
  • 68