The easiest example for modulus arithmetic is "clock" arithmetic, that is, counting hours on a n-hour clock, if your modulus is n :

   4 =~ 8 =~ 0 =~ -4 =~ -8 (4)
   3 =~ 4 == 3             (4)
  -3 =~ 4 == 1 =~ 4 == 1   (4)
[download]

In principle, while the value is not within the range 0..n-1, you add/subtract the modulus to get closer to that range. So C is "wrong", because C implements the modulus as the remainder of the division, and Perl is right, because it implements the modulus as the modulus.

perl -MHTTP::Daemon -MHTTP::Response -MLWP::Simple -e ' ;    # The  
$d = new HTTP::Daemon and fork and getprint $d->url and exit;#spider
($c = $d->accept())->get_request(); $c->send_response( new   #in the
HTTP::Response(200,$_,$_,qq(Just another Perl hacker\n))); ' #  web
[download]

The word modulus has several different meanings in mathematics with respect to complex numbers, congruences, elliptic integrals, quadratic invariants, sets, etc.

And here is a definition of congruerence which is what should applicable here. It defines the modulus as a set of numbers, so that -3 and 1 are both the modulus for your example. To define the operation well you need to take not the modulus but the common residue which is unique and is nonnegative. And this is what does Perl.

It appears nobody has pointed out yet that use integer will make Perl's mod and division operators work just like C's. More precisely, it will use whatever operations the C compiler that compiled perl happens to like.

So, which is mathematically correct?

It's not a matter of what is correct. In math, we get to make up anything we want, and then reason from it. If you don't believe me, you just haven't studied enough higher math. What is important is whether it is consistent and useful. "Division" means that you're given x and d, and you find q and r such that

x = q * d + r

Normally, we like r positive, but that's a matter of convention. As long as the / operator gives you q and % gives you r that work in this equation, things are consistent. All C compilers I know of follow this rule. Perl's division operator doesn't quite follow it, because it returns a floating-point result. You need to do a floor (not int!) after division to get the right result in integer arithmetic.

As to what's useful, when writing number-theoretic algorithms, it is almost always preferable to have the modulus give you a result that's always positive, like Perl's mod operator does.

In math, we get to make up anything we want, and then reason from it. If you don't believe me, you just haven't studied enough higher math. What is important is whether it is consistent and useful.

Well, I did study higher maths. And your argumentation is basically right. For example, if you ask how much is 2+2? one should reply it depends. Why? Because you ain't saying anything about the base on which respect you are calculating the result (e.g., 2+2=0 in the weird 4-based Z(4) numerical system -the integers modulo 4).

But we ain't talking about higher mathematics here, that's plain algebra in the old 10-based numerical system Z, the dear old integer mathematics we studied in the early years of the school, where my teacher used to hit me on my face if I wrote a negative reminder (or one that was too big). And in dear old mathematics the modulus is always positive.

Ciao!
--bronto

Update: thanks to Enlil for pointing errors around; fixed (hopefully :-)

---

The very nature of Perl to be like natural language--inconsistant and full of dwim and special cases--makes it impossible to know it all without simply memorizing the documentation (which is not complete or totally correct anyway).
--John M. Dlugosz

But we ain't talking about higher mathematics here, that's plain algebra in the old 10-based numerical system, the dear old mathematics we studied in the early years...

No, actually we're not talking about that. We're talking about programming, so we're talking about what computers do. And what most of them do nowadays is implement a single instruction that does a truncating divide and gives you a quotient and remainder from that operation. Some extended-precision arithmetic packages (like GMP) give you both round-towards-zero and round-towards-negative-infinity (in other words, positive remainder) division routines, but that's as maybe.

As the co-worker who ran smack into this problem, I think the question that I would really like to find out is:
So, which is the more common result?
I can see both of these being solutions to that equation:


x = q * d + r
-7 = 4 * d + r

So for d = -1, r = -3
And for d = -2, r = 1
[download]

In the code I'm writing I have use for both of these results, so neither is more or less correct. I just thought that there was a commonly accepted algorithm (as there is for positive modulo) for this.
I think it really comes down to how the rounding operation works.

So, which is the more common result?

Unfortunately, there's no good answer. Hardware vendors choose different ways of implementing division, because division is complicated. Language specifications usually let the compiler go with whatever the underlying hardware does, for speed. Division with round-towards-zero (which can produce a negative remainder) is common in modern systems, but nobody is making you any guarantees.

If getting consistent results across different platforms is important to you, you can always calculate the remainder by hand.

$q = int($x / $d);
$r = $x - $d * $q;
[download]

Of course, that costs you an extra multiply and subtract.

I think it really comes down to how the rounding operation works.

Precisely.

The question is "Which is the more commonly accepted result?". The answer to that is the positive number. Perl is right, C is wrong (but quicker, if you're into that sort of thing).

------
We are the carpenters and bricklayers of the Information Age.

Don't go borrowing trouble. For programmers, this means Worry only about what you need to implement.

Please remember that I'm crufty and crochety. All opinions are purely mine and all code is untested, unless otherwise specified.

The reminder of a division is, by definition, a positive number. So the answer "-3" is plain wrong.

Ciao!
--bronto

Update: To be exact: if n and m are an integer numbers (i.e. 0, -1, 1, -2, 2...) there is a unique decomposition of the form:

with r and q integers and |n| > r >= 0. q is said to be the quotient and r the reminder

That's why a negative reminder is wrong by definition

Update: fixed a typo.

The very nature of Perl to be like natural language--inconsistant and full of dwim and special cases--makes it impossible to know it all without simply memorizing the documentation (which is not complete or totally correct anyway).
--John M. Dlugosz

------
We are the carpenters and bricklayers of the Information Age.

Don't go borrowing trouble. For programmers, this means Worry only about what you need to implement.

Please remember that I'm crufty and crochety. All opinions are purely mine and all code is untested, unless otherwise specified.

The important thing about the modulus operator is that the results are consistent with integer division. i.e., if you divide the modulus by the divisor and add it to the result of integer division you get the actual quotient. In Perl, you can test that like this:

I think I got that right. Anyway, you get the idea. The point of the modulus is that it gives you the correct amount of "left over", the amount by which integer division is off.

Some languages have a special integer division operator (usually spelled div), but AFAIK Perl doesn't, so the int truncation is the way integer division is done, then.

So I suspect that Perl has defined the mod operator (spelled %) in such a way as to keep the above assertion intact given the way int truncates. So the real question you want to ask is about why integer division is not consistent between all languages. Why do some langauges truncate down and others always truncate toward zero?

And I think the answer to that probably comes down to hysterical raisins, but I don't know the details.

for(unpack("C*",'GGGG?GGGG?O__\?WccW?{GCw?Wcc{?Wcc~?Wcc{?~cc'
.'W?')){$j=$_-63;++$a;for$p(0..7){$h[$p][$a]=$j%2;$j/=2}}for$
p(0..7){for$a(1..45){$_=($h[$p-1][$a])?'#':' ';print}print$/}
[download]

Forgot to mention: if I recall my study of equivalence classes in modern algebra correctly, the way Perl does this is the more mathematically correct way (because e.g., seven is equal to negative two modulo three IIRC; they are both in the 1 class). But that is far less imporant for programming purposes than getting the modulus consistent with int division, because all sorts of things will break if those aren't consistent. Whole algorithms would be untenable.

---

for(unpack("C*",'GGGG?GGGG?O__\?WccW?{GCw?Wcc{?Wcc~?Wcc{?~cc'
.'W?')){$j=$_-63;++$a;for$p(0..7){$h[$p][$a]=$j%2;$j/=2}}for$
p(0..7){for$a(1..45){$_=($h[$p-1][$a])?'#':' ';print}print$/}
[download]