% operator

[Bazzy]

According to the standard:

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⁷⁴⁾

74) According to work underway toward the revision of ISO C, the preferred algorithm for integer division follows the rules defined in the ISO Fortran standard, ISO/IEC 1539:1991, in which the quotient is always rounded toward zero.

From what i know, -5 mod 7 should give 2 as result.
Wolfram|Alpha thinks the same: http://www.wolframalpha.com/input/?i=-5+mod+7
But on gcc -5 % 7 gives -5

Why is the modulo operator different in C++ from mathematics?
This can be confusing

[kbw]

Isn't that one of the implementation defined conditions from the quote?

[Bazzy]

Only the sign is implementation defined. That should mean that -5 % 7 can return 5 or -5

[z05DSL3A]

Why is the modulo operator different in C++ from mathematics?

http://en.wikipedia.org/wiki/Modular_arithmetic might hold the answer you are looking for.

[1yR4jE8b]

Why would -5 % 7 give 2 as a result? 5 / 7 is 0 with 5 remainder, and like the standard says, signed modulus is implementation specific, so -5 % 7 could give either -5 or 2. They chose to keep the one with the same sign as the dividend.

I don't understand where the confusion is?

[Bazzy]

From what I've been taught:

a ≡m b ⇔ a and b have the same remainder in the Euclidean division by m ⇔ a-b = km

-5 / 7 = -1 * 7 + 2
two is the reminder

-5 mod 7 = 2
2 mod 7 = 2

2+-5 = 2+5 = 7 = 1*7

[z05DSL3A]

Why would -5 % 7 give 2 as a result?

Lets say you had a wired clock that that has only 7 hours on it.
If you start at the top of the clock and go forward one hour it is 1 o'clock. 1 = 1 (mod 7)

Start at the top again and wind forward 8 hours and the clock reads 1 o'clock. 8 = 1 (mod 7)

If you stat at the top and wind the clock back 5 hour (-5) then the clock face reads 2 o'clock. -5 = 2 (mod 7)

So in maths if you do if you do -5 mod(7) you should have 2 in modulo 7, in programming the modulo operator calculates the remainder and doesn't give the congruent modulo value.

Edit:
NB: = in this case is meant to be a congruence relation; so 8 = 1 (mod 7) should be read as 8 is congruent to 1 in modulo 7.

[1yR4jE8b]

-5 / 7 = -1 * 7 + 2

That's one possibility, there is also

-5 / 7 = 0 * 7 - 5

Which is what GCC and Visual C++ 2010 uses, it's kinda like Price is Right, take the quotient that is "Closest to, without going over"

Even in mathematics, the modulo operation for negative integers is ambiguous. Although, I agree with the "Price is Right" logic when dealing with programming.

[Bazzy]

The reminder should be 0 < r < m

[1yR4jE8b]

That only applies for non-negative integers.

with negative, we get either


ceil(-5/7) + r or floor(-5/7) + r, either way is correct but *to me* floor(-5/7) +r makes more sense.

[Bazzy]

I've been studying integers and euclidean division for 6 months.
The definition of the remainder on integer division using the euclidean algorithm is to be a number greater or equal to zero and less than the number you are dividing by.
Anything else is not a remainder

[1yR4jE8b]

Then I guess we should call up Redmond and the Gnu Foundation and tell them to rewrite their compilers, while we're at it let's phone up Intel and tell them their idiv instruction is wrong.

I agree with you that yes, in number theory, we tend to choose the positive one, other people choose the negative one. We're talking about it in the context in C++ which makes the latter solution the correct one, in context.

There is no unique solution, you can show me a proof that yours is correct but I can (and have) given you a counter example. This makes it ambiguous so you just have to pick one and go with it.

I'm not trying to tell you that you are wrong, I'm just saying, it's ambiguous and either result is acceptable.

[Bazzy]

I've just been to a lecture on Algorithms and Data structure. The lecturer defined the remainder the same way I did in my previous post.
BTW I'm not complaining about the sign of the value returned by the % operator but of its value.
abs( -5 % 7 ) != 2

[Disch]

I didn't read that link Bazzy posted, but anyway....

I agree that abs( -5 % 7 ) == 2 would be far more useful and more logical.

If you figure... you have x % y... then logically (x-1) % y would be 1 less (unless x%y was zero, in which case you'd have y-1).

This would jive with how 2's compliment and & work, too. If you figure that x&7 is a "shortcut" for x%8:

9 & 7 = 1
8 & 7 = 0
7 & 7 = 7
...
1 & 7 = 1
0 & 7 = 0
-1 & 7 =7

So logically you'd expect %8 to work the same way, yet...

9 % 8 = 1
8 % 8 = 0
7 % 8 = 7
...
1 % 8 = 1
0 % 8 = 0
-1 % 8 = 1  // wtf?  why not 7? 

On the other hand....

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

This makes some sense, too.

-5%7 = -5 makes perfect sense when you consider the above equation. After all, -5/7 is 0 with a remainder of -5. Unless you want -5/7 to be -1 with a remainder of 2 (but ugh).

Maybe a second operator would be better. Like % for modulus like we have now, and %% for the more "AND-like" approach. I don't know how that would fly with the compiled assembly, though.

[chrisname]

There's no logical instructions in x86 assembly. You can do bitwise AND, OR, NOT, XOR and you can do SHL and SHR (shift left and shift right respectively) and you can couple that with use of conditional jumps to get a similar effect, but it's untidy.

[imi]

so.. what about just using this?

template<class T>
T remainder(T a, T b) { return (a>0) ? a%b : a%b+abs(b); }

Unless I made a mistake, this should always give you the positive remainder 0 <= x <= |b|-1, regardless of a and b on those compilers returning -5 in your example.

[Bazzy]

That is not the right formula, it will return 2 in this example: -8 % 2
This seems to work: int modulo (int m, int n) { return m >= 0 ? m % n : ( n - abs ( m%n ) ) % n; }

[z05DSL3A]

The reminder should be 0 ≤ r < m

The lecturer defined the remainder the same way I did in my previous post.

Here are some other definitions:
For natural numbers: a = qd + r and 0 ≤ r < d.
For integers: a = qd + r for some integer q, and with 0 ≤ |r| < |d|.
For real numbers with q constrained to being an integer: a=qd+r with 0 ≤ r < |d|. if the remainder is required to be negative then -|d| < r ≤ 0.

Real number remainder is generally implemented for programing languages IIRC.