CODEWITHSUNDEEP
cdivisionmodulointeger-division
towi
towi

Reputation: 22267

C remainder/modulo operator definition for positive arguments

I found a function in a program I am supposed to fix that has a mod function defined:

int mod(int a, int b)
{
  int i = a%b;
  if(i<0) i+=b;
  return i;
}

I was told that a and b will always be positive by the way...

Huh? if(i<0)?

The argument is, that

the result of the modulo operation is an equivalence class, and any member of the class may be chosen as representative

And only as an afterthought

...; however, the usual representative is the least positive residue, the smallest nonnegative integer that belongs to that class, i.e. the remainder of the Euclidean division. However, other conventions are possible.

That means that 6 % 7 could return 6 (so far so good), but also -1. Hrm... really? (Lets ignore the fact that the presented implementation does not handle all cases.)

I know that it is mathematically true that the modulo operation is like this. But then someone else told me that the C % does in fact "not implement the modulo operator but the remainder".

So, how does C define the % operator?

In the C-Draft I only find

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.

Does this mean, that 6 % 7 is always 6? Or can it be -1, too?

Upvotes: 4

Views: 1209

Answers (4)

Davide Spataro
Davide Spataro

Reputation: 7482

According to the standard:

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

This means that the sign of a is preserved in the modulo.

 17 %  3  ->  2
 17 % -3  ->  2
-17 %  3  -> -2
-17 % -3  -> -2

So no, 6%7 cannot be -1 because the reminder has to have the same sign of the dividend.

Upvotes: 6

Steve Summit
Steve Summit

Reputation: 47952

There are at least three different ways of defining the division and remainder algorithms when one number or the other might be negative. (See this Wikipedia article -- and particularly the nice picture there -- for more details.)

But if you know you're dividing a positive number by a positive number, there's no ambiguity whatsoever. All three definitions of division and remainder say that if you're dividing a positive number by a positive number, you get a positive quotient and a positive remainder.

Of the three options there, C uses the one called "truncating division". But, again, for positive numbers, it doesn't make any difference. (Once upon a time, it was up to the compiler whether it used truncating or "Euclidean" division, but things settled down on just the one definition, several revisions of the C Standard ago.)

Does this mean, that 6 % 7 is always 6? Or can it be -1, too?

Yes, 6 % 7 is always 6 (in C, and under any of the three definitions).

See also this epic, related question.

Upvotes: 2

AProgrammer
AProgrammer

Reputation: 52294

Forever:

  • a == (a/b)*b + a%b
  • abs(a%b) < abs(b)
  • if a and b are positive, a % b is positive.

Since C99,

  • a/b == trunc(a/b)
  • a%b is either 0 or has the sign of a.

Thinking that 6 % 7 could be -1 is probably due to missing the fact that the result for a and b positive has always been guaranteed and missing the change in C99.

Upvotes: 5

Blaze
Blaze

Reputation: 16876

Does this mean, that 6 % 7 is always 6? Or can it be -1, too?

According to this documention:

Remainder

The binary operator % yields the remainder of the division of the first operand by the second (after usual arithmetic conversions).

[...]

when the type after usual arithmetic conversions is an integer type, the result is the algebraic quotient (not a fraction), rounded in implementation-defined direction (until C99)truncated towards zero (since C99)

So 6 / 7 will be 0, and 6 % 7 will be 6 - 0, which is 6.

The claim about modulo operations and equivalence classes is interesting, that's not how it works in C (and most other programming languages).

Besides, even if that were the case, wouldn't -8 be in the same equivalence class? Then if(i<0) i+=b; wouldn't solve the problem.

But then someone else told me that the C % does in fact "not implement the modulo operator but the remainder".

Good point. In the documentation that I linked, it is called the "Remainder".

Upvotes: 2

Related Questions