Beefy Boxes and Bandwidth Generously Provided by pair Networks
more useful options
 
PerlMonks  

Modulus Inconsistencies (Or Calling all Mathematicians)

by RollyGuy (Chaplain)
on Mar 26, 2003 at 16:12 UTC ( #245974=perlquestion: print w/replies, xml ) Need Help??

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 C-based 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?

Replies are listed 'Best First'.
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 n-hour 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..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
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.

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 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
      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;

        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.

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 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
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 .. ($n-1). 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.

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[$p-1][$a])?'#':' ';print}print$/}

      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$/}
Re: Modulus Inconsistencies (Or Calling all Mathematicians)
by Anonymous Monk on Mar 27, 2003 at 02:22 UTC
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

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://245974]
Approved by sschneid
Front-paged by Enlil
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others rifling through the Monastery: (5)
As of 2022-08-10 17:11 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?