20

Is it guaranteed that in C++11, (-x) % m is negative and equal to (-x % m), where x and m are positive?

I know it's right on all machines I know.

Jan Schultke
  • 17,446
  • 6
  • 47
  • 96
RiaD
  • 46,822
  • 11
  • 79
  • 123

2 Answers2

11

In addition to Luchian's answer, this is the corresponding part from the C++11 standard:

The binary / operator yields the quotient, and the binary % operator yields the remainder from the division of the first expression by the second. If the second operand of / or % is zero the behavior is undefined. For integral operands the / operator yields the algebraic quotient with any fractional part discarded; if the quotient a/b is representable in the type of the result, (a/b)*b + a%b is equal to a.

Which misses the last sentence. So the part

(a/b)*b + a%b is equal to a

Is the only reference to rely on, and that implies that a % b will always have the sign of a, given the truncating behaviour of /. So if your implementation adheres to the C++11 standard in this regard, the sign and value of a modulo operation is indeed perfectly defined for negative operands.

Christian Rau
  • 45,360
  • 10
  • 108
  • 185
  • Hmm, you use that `a/b` is rounded to zero. is it really? – RiaD Oct 03 '12 at 14:52
  • 2
    @RiaD It's just in the sentence before: *"For integral operands the / operator yields the algebraic quotient with any fractional part discarded"*. – Christian Rau Oct 03 '12 at 14:53
  • Oh, but I don't really sure what it means. because In our school and university we call `fractional part` positive number [0...1) and the integer part max number that is not great than x, i.e [-1.5] is -2 – RiaD Oct 03 '12 at 14:56
  • @RiaD I don't know if it is really free for interpretation. You got `4.2`, drop the fractional part (the numbers behind the `.`) and you get `4`. Take `-4.2`, again drop the fractional part and get `-4`. What you talk about is the *floor* function, a special rounding method. But the standard talks about discarding the fractional part, which doesn't alter the numbers before the `.` in any way, it just removes the numbers after the `.`. – Christian Rau Oct 03 '12 at 15:00
  • Oh, I see. There isannotation 80, that say what I want. – RiaD Oct 03 '12 at 15:00
  • Oh golly and drat! I can;t believe they got this wrong. Yes, I said wrong,and I meant wrong. The mathematical, and the sensible way, is to round down, so that the result is always positive. Otherwise, every application that actually uses modulo on negative values will require a test. Try to find a counter-example. I define a function to encapsulate the test, which is to say, return the real modulus value, int mod(int x, int y) { int ret = x%y; if(ret<0) ret += y; return ret; } – Jive Dadson Nov 17 '16 at 02:32
7

5.6 Multiplicative operators

4) The binary / operator yields the quotient, and the binary % operator yields the remainder from the division of the first expression by the second. If the second operand of / or % is zero the behavior is undefined; otherwise (a/b)*b + a%b is equal to a. If both operands are nonnegative then the remainder is nonnegative; if not, the sign of the remainder is implementation-defined (emphasis mine)

This is from C++03 though. :(

Luchian Grigore
  • 253,575
  • 64
  • 457
  • 625
  • 1
    I believe that this was not changed in c++0x, to maintain backward compatibility. – Patrick White Oct 03 '12 at 14:43
  • @PWhite In fact Wikipedia says it was changed to defined behaviour, I'll dig it up in the standard. – Christian Rau Oct 03 '12 at 14:46
  • I think the last part (in bold here) was removed in the C++11 standard (at least, it is removed in the draft I have). Anyway, I don't see how the previous equality could hold if the remainder was not negative. Take for instance `a=-3` and `b=2`: if `a%b` is not negative, then `(a/b)*b + a%b` => `(-3/2)*2 + -3%2` => `-2 + 1` => `-1`, which is not equals to `-3`. Or am I missing something? – Luc Touraille Oct 03 '12 at 14:49
  • @Luc: In C++03 it's permissible for `-3 % 2` to be `1` provided that `-3 / 2` is `-2`. Your calculations assume `-3 / 2 == -1`, which is not guaranteed in C++03 (or in C89 btw). Although the standard only explicitly talks about the sign of `%`, because of the relation `(a/b)*b + a%b == a` it is of course *also* dictating the rounding direction for integer division: negative modulus => round-toward-zero, positive modulus => round-toward-negative-infinity. C99 and C++11 both tightened what was previously implementation-defined. – Steve Jessop Oct 03 '12 at 15:24
  • 1
    And the nice property of round-towards-zero is of course the very thing questioner is asking about: `(-x) % m == -(x %m)` and `(-x) / m == -(x / m)`. Conversely the nice property of round-towards-negative-infinity is that there are only `m` possible values for the modulus, and these values are the elements of the mathematical ring of integers modulo `m`. – Steve Jessop Oct 03 '12 at 15:28
  • @SteveJessop: I always thought the behavior of division was well-defined (I mean, how could a language leave something like this implementation-defined for such a long time :-/!?), but I was indeed wrong. For the record, I stumbled upon [this related question](http://stackoverflow.com/q/319880/20984). – Luc Touraille Oct 03 '12 at 15:36
  • @Luc: meh, the behavior of addition is sometimes undefined (overflow), narrowing conversions are implementation-defined. So we counted ourselves lucky we were allowed negative operands to `/` at all ;-) It's quite easy to "fix" both `/` and `%` to get the rounding you want, and would be even if it was unspecified rather than implementation-defined. So it was sometimes a bit annoying but I don't think the implementation-definedness was ever a massive deal. It is probably *better* to make uncommon CPUs slower, than to have everyone need to check it whenever they write supposedly-portable code. – Steve Jessop Oct 03 '12 at 15:46
  • @SteveJessop, BTW I don't really think, that `(-x) % m == -(x %m)` is very good thing, I just use it for explanation. `m` possible result is much better) – RiaD Oct 03 '12 at 18:42
  • if the part in bold was removed, doesn't that means that we don't even have the guarantee that if both operand are non-negative then result is non-negative? actually 3%2 may yield -1 :P (there is nothing saying anything about the sign XD) – CoffeDeveloper Jan 11 '14 at 10:53