By towi


2019-11-08 14:12:11 8 Comments

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?

4 comments

@Davide Spataro 2019-11-08 14:20:13

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.

@towi 2019-11-08 14:24:28

I did not ask about the sign

@Davide Spataro 2019-11-08 14:25:56

But it answers your question. It cannot be -1 cause 6 is positive.

@Steve Summit 2019-11-08 14:43:01

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.

@AProgrammer 2019-11-08 14:33:46

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.

@Blaze 2019-11-08 14:18:45

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

@Davide Spataro 2019-11-08 14:23:46

Indeed, you would need something equivalent to: while(i<0) i+=b

@towi 2019-11-08 14:26:06

thanks, I have the same interpretation. and my comment "Lets ignore..." was exactly about your last sentence.

@Paul Hankin 2019-11-08 14:31:59

The documentation you link to is wrong. The C89 standard section 6.3.5 specifies "When integers are divided and the division is inexact, if both operands are positive the result of the / operator is the largest integer less than the algebraic quotient and the result of the % operator is positive."

@Paul Hankin 2019-11-08 14:34:02

The rounding of / and sign of % is only impl-defined (pre C99) if one or both operands are negative: "... If either operand is negative, whether the result of the / operator is the largest integer less than or equal to the algebraic quotient or the smallest integer greater than or equal to the algebraic quotient is implementation-defined, as is the sign of the result of the % operator. If the quotient a/b is representable, the expression (a/b) *b + a%b shall equal a. "

@Blaze 2019-11-08 14:38:17

@PaulHankin thanks! That's more credible than the documentation. Do you have a link to this so I can add it to the answer?

Related Questions

Sponsored Content

23 Answered Questions

48 Answered Questions

[SOLVED] Divide a number by 3 without using *, /, +, -, % operators

  • 2012-07-27 19:34:31
  • Green goblin
  • 136975 View
  • 677 Score
  • 48 Answer
  • Tags:   c math division divide

1 Answered Questions

[SOLVED] Understanding Mod Operator in Math vs Programming

15 Answered Questions

[SOLVED] Integer division with remainder in JavaScript?

4 Answered Questions

[SOLVED] What does the C ??!??! operator do?

  • 2011-10-19 16:56:59
  • Peter Olson
  • 250703 View
  • 1903 Score
  • 4 Answer
  • Tags:   c operators trigraphs

3 Answered Questions

[SOLVED] Why does C++ output negative numbers when using modulo?

  • 2012-07-24 11:54:52
  • Martin Thoma
  • 20316 View
  • 52 Score
  • 3 Answer
  • Tags:   c++ standards modulo

8 Answered Questions

4 Answered Questions

[SOLVED] Modulo division returning negative number

Sponsored Content