laziness, impatience, and hubris PerlMonks

### Re: Re: 0 illegal modulus?

by jepri (Parson)
 on Jun 14, 2001 at 22:44 UTC ( #88569=note: print w/replies, xml ) Need Help??

in reply to Re: 0 illegal 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.

Replies are listed 'Best First'.
Re^3: 0 illegal modulus?
by Anonymous Monk on Jul 10, 2007 at 08:32 UTC
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"

Re: Re: Re: 0 illegal modulus?
by mugwumpjism (Hermit) on Jun 15, 2001 at 00:20 UTC

"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.

(On reading a book to understand a simple principle)

You obviously don't get it. You can't expect someone who uses the % operator to have read a book on number theory first. Therefore it should behave intuitively and comply with what the commonly accepted understanding of the term is, so long as it is sensible and consistent. I think I have demonstrated in other posts that a modulus of 0 is neither sensible nor consistent, except with one contrived definition of modulus which I still think is bogus.

You say a modulus is defined one way; I say another. Who is to say who is right, or whether being "right" means anything? Let's end this rant and agree to disagree.

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).

Create A New User
Node Status?
node history
Node Type: note [id://88569]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (8)
As of 2017-06-24 08:19 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
How many monitors do you use while coding?

Results (557 votes). Check out past polls.