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.

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"

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?

You say:

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

The answer is "So you know what you are talking about". I admit I was too quick off the gun as well, however. After some further research I found that the modulo function was devised by Abel in the 1700's to allow him to study large and complicated groups with only pencil and paper.

Modulo is hardly a basic operator. It's just a basic operator for you because you've only ever used it in simple situations.

Computer implementations of functions are usually nasty bastardisations of real math functions. This is why the original poster mentioned Knuth, who did a lot of work involving math and computers.

Incidentally, 'proof by random web pages' is a poor way of proving that you are right.

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

You write: 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. Yes, and the difference between no two different integers is divisible by zero. Therefore all integers are in different congruence classes mod 0, which is another way of saying that x mod 0 = x, as the original poster claimed. Although of course it's a matter of definition whether (1) an integer is then congruent to itself mod 0 and (2) the mod "operator" is actually that closely related to the mod "arithmetic" that it returns the name of the congruence class under arithmetic mod that number. % is probably better called "remainder" than mod, anyhow, and again it makes sense for x % 0 to be x when you talk about remainders. No matter how often you subtract zero, x remains... (but that's the same argument others have made).

Let me explain further:

You have the integers:

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

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.