% operator

Feb 12, 2010 at 2:21pm
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-defined74)

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
Feb 12, 2010 at 2:52pm
Isn't that one of the implementation defined conditions from the quote?
Feb 12, 2010 at 2:56pm
Only the sign is implementation defined. That should mean that -5 % 7 can return 5 or -5
Feb 12, 2010 at 3:19pm
closed account (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.
Feb 12, 2010 at 3:30pm
closed account (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?
Last edited on Feb 12, 2010 at 8:03pm
Feb 12, 2010 at 3:50pm
From what I've been taught:

am ba and b have the same remainder in the Euclidean division by ma-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
Last edited on Feb 12, 2010 at 3:53pm
Feb 12, 2010 at 4:02pm
closed account (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.
Last edited on Feb 12, 2010 at 4:27pm
Feb 12, 2010 at 4:46pm
closed account (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.
Last edited on Feb 12, 2010 at 4:48pm
Feb 12, 2010 at 4:57pm
The reminder should be 0 < r < m
Feb 12, 2010 at 5:42pm
closed account (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.
Feb 12, 2010 at 5:48pm
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
Feb 12, 2010 at 6:40pm
closed account (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.
Feb 23, 2010 at 3:48pm
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
Feb 23, 2010 at 6:34pm
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:
1
2
3
4
5
6
7
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...
1
2
3
4
5
6
7
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.
Feb 23, 2010 at 6:46pm
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.
Last edited on Feb 23, 2010 at 6:46pm
Feb 24, 2010 at 12:57pm
so.. what about just using this?

1
2
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.
Last edited on Feb 24, 2010 at 12:57pm
Feb 24, 2010 at 2:44pm
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; }
Last edited on Feb 24, 2010 at 2:44pm
Feb 24, 2010 at 4:13pm
closed account (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.

Last edited on Feb 24, 2010 at 4:35pm
Topic archived. No new replies allowed.