RollyGuy has asked for the wisdom of the Perl Monks concerning the following question:
A coworker of mine pointed out that C and Perl think differently when it comes to the modulus operator. For all positive number, the two agree, but when the modulus of a negative number is taken, there are differences.
Using a Cbased calculator, I have:
> (7)%4
= 3.000000 (0000000000000000)
Using perl, I have: my $val = (7)%4;
print "ANS1 = $val\n";
Output:
ANS1 = 1
So, which is mathematically correct? I think that maybe the C version is correct because modulus give us the residue (or remainder) of a division function. 7/4 gives (1 3/4) as an answer, so 3 seems to be the correct remainder. Any thoughts?
Re: Modulus Inconsistencies (Or Calling all Mathematicians)
by Corion (Patriarch) on Mar 26, 2003 at 16:24 UTC

The easiest example for modulus arithmetic is "clock" arithmetic, that is, counting hours on a nhour clock, if your modulus is n :
4 =~ 8 =~ 0 =~ 4 =~ 8 (4)
3 =~ 4 == 3 (4)
3 =~ 4 == 1 =~ 4 == 1 (4)
In principle, while the value is not within the range 0..n1, 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
 [reply] [d/l] [select] 
Re: Modulus Inconsistencies (Or Calling all Mathematicians)
by zby (Vicar) on Mar 26, 2003 at 16:38 UTC

I have searched the mathworld.wolfram.com and here is what I found:
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.  [reply] 
Re: Modulus Inconsistencies (Or Calling all Mathematicians)
by no_slogan (Deacon) on Mar 26, 2003 at 18:03 UTC

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 floatingpoint 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 numbertheoretic algorithms, it is almost always preferable to have the modulus give you a result that's always positive, like Perl's mod operator does.
 [reply] 

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 4based Z(4) numerical system the integers modulo 4).
But we ain't talking about higher mathematics here, that's plain algebra in the old 10based 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 languageinconsistant and full of dwim and special casesmakes it impossible to know it all without simply memorizing the documentation (which is not complete or totally correct anyway).
John M. Dlugosz
 [reply] 

But we ain't talking about higher mathematics here, that's plain algebra in the old 10based 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 extendedprecision arithmetic packages (like GMP) give you both roundtowardszero and roundtowardsnegativeinfinity (in other words, positive remainder) division routines, but that's as maybe.
 [reply] 

As the coworker 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
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.  [reply] [d/l] 

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 roundtowardszero (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;
Of course, that costs you an extra multiply and subtract.
I think it really comes down to how the rounding operation works.
Precisely.  [reply] [d/l] 

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.
 [reply] 
Re: Modulus Inconsistencies (Or Calling all Mathematicians)
by bronto (Priest) on Mar 26, 2003 at 17:57 UTC

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:
n = mq + r
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 languageinconsistant and full of dwim and special casesmakes it impossible to know it all without simply memorizing the documentation (which is not complete or totally correct anyway).
John M. Dlugosz
 [reply] [d/l] [select] 
Re: Modulus Inconsistencies (Or Calling all Mathematicians)
by dragonchild (Archbishop) on Mar 26, 2003 at 16:50 UTC

By the 8th grade definition of modulus, C is closer to being wrong (or Perl is more right). Modulus is usually a number in the range 0 .. ($n1). However, it isn't "wrong" to be in the range (1  $n) .. 0. It's just not the way most people think about it. (Kinda like saying 10/20 instead of 1/2 ...)
 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.  [reply] 
Re: Modulus Inconsistencies (Or Calling all Mathematicians)
by jonadab (Parson) on Mar 27, 2003 at 01:50 UTC

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:
((($a%$b)/$b)+(int($a/$b)))==($a/$b)
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[$p1][$a])?'#':' ';print}print$/}
 [reply] [d/l] [select] 

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[$p1][$a])?'#':' ';print}print$/}
 [reply] [d/l] 
Re: Modulus Inconsistencies (Or Calling all Mathematicians)
by Anonymous Monk on Mar 27, 2003 at 02:22 UTC

 [reply] 
Re: Modulus Inconsistencies (Or Calling all Mathematicians)
by aquarium (Curate) on Mar 27, 2003 at 03:05 UTC

has anyone considered yet that it may be valid to
perform 7%4 as (7%4)..so 3 is valid. Generally, computer implementations for math other than binary are weak when they use floating point math. It's always a matter of how close is good enough...ask a scientist.
Chris  [reply] 

