Zugg Software :: View topic

Magician Joined: 23 Apr 2003 Posts: 358 Location: USA

When calculating in modular arithmetic, 0 <= n modulo m < m always. However, when using %mod(n,m) with a negative n, I get a negative value.

For example, -1 (mod 3) ≡ 2, but CMUD calculates %mod(-1,3) = -1.

Posted: Fri Sep 02, 2011 1:20 am

It's not a bug, it is that way by design. CMUD's modulo function works the way it does in C#, that is, it takes the sign from the dividend.

NOTE: Yes, I agree that this behavior does not conform to the mathematical definition.

Wanderer Joined: 24 May 2005 Posts: 71

In most coding languages, the mod function behaves the same way. That is, computer science mod is different from mathematical mod.

Magician Joined: 23 Apr 2003 Posts: 358 Location: USA

Good to know. I can modify my code involving %mod accordingly, but it bothers the hell out of me (being a professional mathematician).

Posted: Fri Sep 02, 2011 2:21 am

Try this:

rather than just use m = x % y, use m = (x + y) % y.

This will work for most practical values of x. If x is significantly small, then the dividend can be adjusted further, but this gets to be a bit kludgy.

Magician Joined: 23 Apr 2003 Posts: 358 Location: USA

Here's my fix:

Posted: Fri Sep 02, 2011 3:58 pm

I'm still a little confused given 0 <= n modulo m < m because surely with negative n that no longer holds true 0 is not less than or equal to -1 it is greater than.

Magician Joined: 23 Apr 2003 Posts: 358 Location: USA

From number theory:
If a+b=c, then c-a=b.
So, if 3+4=2 (mod 5), then 2-3=4 (mod 5).
Certainly, 2-3=-1.
Thus, -1=4 (mod 5).

n (mod m) is only defined if n is an integer and m is an integer greater than 1.

Posted: Mon Sep 05, 2011 4:11 pm

Again I find that odd because I would define a = 3, b = 4 and c = 2 (mod 5) so altering the equation I would have 2 (mod 5) - 3 = 4, I don't see how you can have that (mod 5) just floating around orphaned on the right hand side as clearly 3 + 4 does not equal 2.

Magician Joined: 23 Apr 2003 Posts: 358 Location: USA

The (mod 5) is a reference to the partition rule of integers for the entire equation. In modular arithmetic, -10=-5=0=5=10=15=20 (mod 5) and -9=-4=1=6=11=16=21 (mod 5), etc. while -12=-6=0=6=12 (mod 6) and -11=-5=1=7=13 (mod 6). Strictly speaking, all of these equals should be ≡ signs, or "congruent to".

One way of understanding modular arithmetic is to define it as remainders. 1=7=13 (mod 6) because when 7 or 13 is divided by 6, the remainder is 1. (Hence, 3+4=2 (mod 5) This definition is what is apparently used by C# (a language I have not studied or used), so the negatives work differently than what I described above from formal Number Theory.

Wanderer Joined: 24 May 2005 Posts: 71

There are languages that provide both a mod function and a remainder function (in Ruby, modulo and mod, respectively) to deal with the discrepancy involving sign. This discrepancy definitely dates to before C#, and likely before C++. I wish I could say that in languages lacking separate functions (or, equivalently, operators) the mod function (or % operator) always works the same way - as a remainder function. But there are minor differences between languages, e.g. in C++ the sign of the result depends on the sign of the first argument, while in Python the sign of the result depends on the second argument.