Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
PerlMonks  

0 illegal modulus?

by nella (Novice)
on Jun 11, 2001 at 05:36 UTC ( #87384=perlmeditation: print w/ replies, xml ) Need Help??

Upon writing $a % 0 I am told that 0 is an illegal modulus.

However, according to "Concrete Mathematics: A Foundation for Computer Science", by Graham, Knuth (yes, that Knuth) and Patashnik 2nd ed. (page 82)
x mod y is defined as x - y{x/y} (where {} is floor) for y!=0, and x mod 0 is defined to be x.
This definition is justified; it preserves the property that x mod y always differs from x by a multiple of y, and makes sense if you think of it this way: x mod y means "map y to 0", so if y already is 0, then there is nothing to do, and x mod 0 should be congruent to x.

Yes, I know that division by 0 is a Bad Thing, but technically we are not dividing, we are defining the mod operator.

So this is more of a rant than a question, but it annoys me to lose functionality from one of my favourite operators in such an amusing language as Perl.

Comment on 0 illegal modulus?
Download Code
Re: 0 illegal modulus?
by Vynce (Friar) on Jun 11, 2001 at 07:11 UTC

    well, you could override the modulus operator if you prefer, and use an idiom like

    $ans = ($y*1) ? $x % $y : 0;
    see overload for details.

    .
Re: 0 illegal modulus?
by Cybercosis (Monk) on Jun 12, 2001 at 00:59 UTC
    Well, had I designed the Perl interpreter (*chuckle*), I'd've made sure that mod 0 was illegal for consistancy with the assembly language on most (that I've dealt with) platforms. For instance, on the x86, the modulus is calculated by doing and I?DIV instruction, which leaves the remainder of the division (the modulus) in the appropriately sized register (AH, DX, or EDX). The brief upshot of this is that, since the modulus is actually calculated with a division, modulus 0 would give you a divide by 0 error. More of an explanation than a solution, really.
Re: 0 illegal modulus?
by nella (Novice) on Jun 12, 2001 at 01:04 UTC

    I think that should be:

    $ans = $y ? %x % $y : $x

    Yes, this would work (but it still seems hackish). Thanks for the advice.

      well, i actually said $y*1 to force that into a numerical context. if you don't, then what if $x is 5 and $y is 'foo'?

      bash-2.04$ perl -e 'print 5 % foo' Illegal modulus zero at -e line 1.
      so...
      bash-2.04$ perl -e '$x = 5; $y = "foo"; print ($y ? $x % $y : $x); pri +nt "\n"' Illegal modulus zero at -e line 1. bash-2.04$ perl -e '$x = 5; $y = "foo"; print ($y*1 ? $x % $y : 0); pr +int "\n"' 0 bash-2.04$ perl -e '$x = 5; $y = "foo"; print (($y*1) ? $x % $y : $x); + print "\n"' 5

      as you can see, one still generates an error. as for what to return if $y is zero, i had misread your original statement.

      .
        Dont use *1! Surely "foo" *is* an illegal modulus. And "0" is still false.
Re: 0 illegal modulus?
by mugwumpjism (Hermit) on Jun 12, 2001 at 18:31 UTC

    A modulus of 0 makes no sense to a non-mathematically trained person. Your explanation of "mod" meaning "mapping" makes no sense the way you wrote it, either.

    Who cares what Knuth said, anyway? His name should not add any weight to his arguments.

    Every definition of modulus that turned up in a quick scan of mine uses the word "remainder" and implies division by the modulus.

    Update: Clarified and toned down my first paragraph

      Let me explain further:

      You have the integers:

      1 2 3 4 5 6 7 9 10 11 ...

      If you consider these numbers mod 4, for example, the integers become:

      1 2 3 0 1 2 3 0 1 2 3 ... (*)

      So you can think of mod as a function (mapping) that takes all multiples of 4 to 0; 4*x mod 4 = 0 for all integers x. Now, the period of repitition in line (*) is obviously 4. (Since the multiples of 4 are all 4 integers apart, and only these are mapped to 0, the period must be 4.) It is similarly true in general that the period of repition is equal to the modulus. (Side note: this is true in the other degenerate case, mod 1. x mod 1 = 0 for every integer x.) What does a period of 0 mean, then, but that there is no repitition. A modulus of 0 does make sense; just as before, it means map multiples of the modulus to 0. The only multiple of 0 is 0, and so only 0 is mapped to 0. As there is no repitition, x mod 0 must be x.

      I hope this is clearer.

        I suppose that could be one flawed way to look at it. But that's got nothing to do with the common definition of the term, the etymological roots of the word "modulus", or what happens when you run this C program:

        #include <stdio.h> int main() { int a,b,c; a=4; b=0; c=a % b; printf ("%d mod %d = %d\n", a,b,c); } $ gcc test.c -o test $ ./test Floating point exception $

        The flaw in your statement is the comment "What does a period of 0 mean, then, but that there is no repitition." I'm sorry, but even if it means that a commonly used integer operation can be used in such a way to produce a divide by zero error, zero times any number is still zero and hence zero cannot be used as a base for a modulus.

      Actually, if I recall my number theory classes correctly, the intent of the modulus operator (x mod y) is to return the smallest number possible by repeatedly subtracting y from x.

      The shortcut is to divide x by y, but not all modular sets support a division operator - the natural numbers, for instance. In these cases, you have to go with the original definition. Since x - 0 - 0 - 0 - 0 - 0... is clearly x,  x mod 0 = x is the correct answer.

      People care what Knuth says about math, because he was a mathematician. Mathematicians are notoriously 'tight' about definitions, so if Knuth said that x mod 0 should return x then he had a good reason for it - one that might take some advanced math to explain.

      Incidentally a 'mapping' is the mathematical term given to an algorithm, very similar to what a perl programmer would think of as a function. It is a collection of rules that turns one set of numbers into another set of numbers. The perl function map is very similar in spirit to the mathematical map, except that (I don't think) it can generate new array elements for a one-to-many mapping.

      There is often a 'null' map - a function that leaves the original set untouched. This is important for a number of reasons that may strike you as silly

      All these ideas are covered in very rigorous detail in any book that has 'Number Theory' in the title.

      ____________________
      Jeremy
      I didn't believe in evil until I dated it.

        Nice one. Your definition:

        "the intent of the modulus operator (x mod y) is to return the smallest number possible by repeatedly subtracting y from x."

        Clearly provides the behaviour expected by the poster of this article. But who cares?

        Any decision on what the function is or how it is defined is arbitrary, and as other people have said, if you are depending on nella's requested behaviour of mod, then you can always just use a ( $y ? $x % $y : $x ) construct.

        Most people are familiar with division, hence a modulus is often explained as the remainer after dividing $x by $y. This obviously is not correct for negative values of $x, unless you count a negative remainder as being a value subtracted from MAXINT (the modulus, in this case) in CS' two's complement tradition.

        If you take a definition from a random hit for "modulo mathematical definition" taken from the WWW, for instance, you'll find the definition:

        Two numbers a and b are said to be equal or congruent modulo N iff N|(a-b), i.e. iff their difference is exactly divisible by N. Usually (and on this page) a,b, are nonnegative and N a positive integer. We write a = b (mod N).

        Note that the difference has to be divisible by N.

        Another page I found expressed it like this:

        number % sub means: map the number on the left-hand side onto the subset {0,sub) (0, zero inclusive, sub exclusive). If sub is negative, this should be (sub,0}, of course.

        Note the words "sub exclusive". Why, then would you map the case where sub == 0 to {-infinity, infinity}? It doesn't follow the pattern.

        Personally, I prefer to think of it in terms of what would the last digit be if expressing this number in base $y? Of course, I think of negative numbers in twos complement form, and consider a negative modulus obfuscated programming (if I came across its use, I'd simply experiment to see what its behaviour was), so this works for me :-)

        Interestingly, C on my platform gets it wrong for negative values of X and positive values of Y. I'm glad Perl doesn't.

        ps. why would I want to read a book on number theory to understand why a basic operator behaves the way it does?

        Here is my bite into the apple.

        jepri gives us an algorythmn .. that does not use division .. to see how this modulus behaves. Let's use it. :)

        > Actually, if I recall my number theory classes correctly,
        > the intent of the modulus operator (x mod y) is to return
        > the smallest number possible by repeatedly subtracting
        > y from x.

        If we are talking number theory we assume non-negative numbers here. So "smallest number" implies here "smallest integer >= 0".
        So.. using Perl integers to emulate natural numbers, we can find the "smallest number" by subtracting until we go negative, and then adding it back on (or storing the number prior to going negative). Let's try:
        $x = 10;
        $y = 0;
        $ans = x;
        while($x>=0)
        {
          $ans -= y;
        }
        $ans +=y #coming back from the grave

        print "$x % $y = $ans\n";

        Hooray! We are using no division operator, so we *cannot* get a divide by zero error! Running this code has *got* to tell us the real answer, once and for all. :) (I .. er.. don't have a perl interpreter handy just now *cough* could one of you guys run this for me, see what we get? kthx)

        On a different note however, I tested the limit of x%y as y approaches zero from the negative and from the positive. But the limit from either direction appears to be zero.. and does not appear to be X.

        This means that setting "x%y=x where y=0" yields a discontinuity at that point. Yes, I know that modulus yields a discontinuous curve whenever you test x against a constant y.. but aside from this example, it never does that when you test y against a constant x.

        To further visualize this discontinuity, draw a map of x%y for a constant y. It looks like sawteeth, with points y units apart and 45 degree inclines. As you make y smaller and redraw the map, the sawteeth get smaller and closer together. Eventually you come to a rough sandpaper across the horizontal axis of your map. This limits to a horizontal line. But Knuth's exception would have it suddenly jump into a single, boundless 45 degree line.

        I cannot fathom the reasion that a person would want such a function to behave that way. Then again, neither can I fathom why anyone would want to round towards zero in a division-enabled modulo calculation.

        I wonder about "x%0 = 0" though, that at least supports the limits we're seeing. It has a certain beauty to it! x divides evenly into 0 undefined times, undefined * 0 is also undefined -- so the remainder would be undefined - undefined = 0. ;) .. come on, it's ok, you can laugh at math jokes :)

        For serious though, I see about as much utility and symmetry to Knuth's exception as I would to "sin(1/x) where x is zero = planck's constant/bunnies"

Because it's not computing congruence
by mugwumpjism (Hermit) on Jun 15, 2001 at 14:20 UTC

    In Mathematics terms, for two numbers A,B to be congruent mod N, then A - B must be an exact multiple of N. So in other words, it is a three argument comparison operator that returns a true/false value, rather than a two argument function like Perl's mod that returns a number between 0 and N-1 (or N+1 and 0 if N is negative).

    But Perl's (and other computer languages') mod operator is based on mapping numbers to what mathematicians call fields; in this case a "wrap-around" set of numbers from 0 to N-1 (or from N+1 to 0 if N is negative). In this context, a field with length 0 doesn't make much sense, so is by default an exception.

    There are good reasons for this; for instance, much code assumes that if A = B mod N, then abs(A) < abs(N). (abs() being the absolute operator). Knuth's decision that "x mod 0 is defined to be x" may make sense to one school of thought, but to another it's bogus.

    If you don't like the behaviour, use a ( $N ? $A % $N : $A ) construct, or see the section in Perl 6 on use limits, which allows you to define the behaviour of this special case.

    Update: OK, IANAM and apparently it's only a field when N is prime. But hopefully you can understand what I mean :)

      Bravo.

      The bogosity in Knuth's argument, for any mathematicians who are interested, is that it is - from the point of view of at least one valid way of working with moduli - a patch for something that wasn't broken, and the Wrong Thing. From the point of view of the theory of limits, it's probably the Right Answer, but that doesn't (necessarily) mean that patching the modulus system to work that way is necessary or desirable.

      I personally think that Perl's mod, and other computer languages', should behave the way Knuth's definition suggests, simply because I'd rather my functions gave answers than not. But I admit that it does, in various ways, break the consistency of the definition to do so.

      Perl 6 is going to have special features for this kind of 'filled in' definition. Can someone enlarge for this relative newcomer on what use limits will do?

      Tiefling (who is imaginary, but appears real at the limit)

      -----BEGIN GEEK CODE BLOCK----- Version: 3.1 GAT d++ s:- a-- C++ UL P++ L++(+) E? W+(++) N+ o? K w+(--) !O M- V? PS+ PE- Y PGP- t+ 5 X+ R+++ tv- b+++ DI++++ D+ G+ e++ h!(-) y +? ------END GEEK CODE BLOCK------
Re: 0 illegal modulus?
by Zaxo (Archbishop) on Jun 16, 2001 at 12:31 UTC

    Everybody, please pay attention to jepri. He's got it right.

    The definition of Abel he mentions is that (perlishly):

    my $num = $y*int($n) + $modulus;

    This relation is uniquely satisfied by !$y && $modulus == $num

    It does not involve division, allowing it to apply to algebrae lacking a multiplicative inverse (those are called modules).

    It applies to floats too. Think $y = 2*$pi. Modulus is phase in that case.

    Perl's % operator is really just remainder on integers, a bogosity which does not generalize well.

    Don't fall into the trap of thinking your intuition or experience is a valid basis for modifying mathematical definitions. You will come to grief when a "proven correct" program crashes. You may blame math, but you will be wrong.

    After Compline,
    Zaxo

    Update: Rereading this, I realize that it sounds directed at nella. Not the case: this is a broadcast rant. nella started a fine thread, and seems to be on the side of the angels.

Re: 0 illegal modulus?
by ambrus (Abbot) on Sep 25, 2005 at 21:56 UTC

      This seems to work great, thank you!

      #use DateTime::Util::Calc qw(mod); #sub mod { $_[1]*1 ? $_[0] % $_[1] : 0);} sub mod { my($x)=$_[0]; my($y)=$_[1]; while($x >= 0){ $x-=$y; } $x+=$y; return($x); }

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlmeditation [id://87384]
Approved by root
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (6)
As of 2014-12-28 10:26 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (180 votes), past polls