in reply to Modulus Inconsistencies (Or Calling all Mathematicians)

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.

  • Comment on Re: Modulus Inconsistencies (Or Calling all Mathematicians)

Replies are listed 'Best First'.
Re: Re: Modulus Inconsistencies (Or Calling all Mathematicians)
by bronto (Priest) on Mar 26, 2003 at 18:13 UTC
    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
[reply]
      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.

[reply]
Re: Re: Modulus Inconsistencies (Or Calling all Mathematicians)
by Helter (Chaplain) on Mar 26, 2003 at 19:02 UTC
    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.
[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 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.

[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]

In Section Seekers of Perl Wisdom