(Numeric) should -7 % 5 = -2 ?

[Steven Taschuk]

Quoth Louis M. Pecora:
  [...]
> The "uniqueness" comes in when we recogize that mod m defines an
> equivalence relation on the integers and so for a given m every integer
> falls into a unique class (or subset of integers).  The set of m
> subsets is equivalent to the positive integers  0 to m-1.  

Or any other complete residue system modulo m; another useful one
is [ floor(-m/2), floor(m/2) ).

> So it appears that the translation between math and computer science is
> not as clear as I thought.  In math (well, number theory) mod is a
> relation, not an operation.  In computer science it is an operation.

Graham, Knuth and Patashnik's _Concrete Mathematics_ (2nd ed.,
1994) claims that "[m]athematicians have used mod [as a binary
operator] informally for a long time, taking various quantities
mod 10, mod 2pi, and so on, but only in the last twenty years has
it caught on formally." (Section 3.4 'mod': The Binary Operation.
There's also a section 4.6 'mod' : The Congruence Relation.)

The question of negative operands is actually two separate
questions, one for the left operand and one for the right operand.

The question for the left operand is easy to a mathematician.  One
normal definition of the relation "congruent modulo m" is
    x == y (mod m)   :=   x - y is a multiple of m
(I use '==' in this post as an ASCII substitute for the three-
lined "is equivalent/congruent to" symbol.)  This directly implies
that, e.g.,
    -7 == 13 (mod 5)
and there is absolutely no question about this in mathematics; it
is essential for, e.g., the result that
    if   a == b (mod m)   and   c == d (mod m)
    then a+c == b+d (mod m)
and many other fundamental properties of congruences.

Now, if we want to call an operator 'mod', surely we want
    x mod m = y mod m    iff    x == y (mod m)
(hereafter "the desideratum").  Thus since (as above)
    -7 == 13 (mod 5)
we must have
    -7 mod 5 = 13 mod 5 = 3
Python's % does this, but Numeric's does not (so Numeric's % is
certainly not mod, though it is a remainder operator).

For negative right operands there is afaik no established
precedent in mathematics.  However, one obvious definition for the
behaviour described so far is
    x mod m   :=   x - m*floor(x/m)
and, given the customary way I've defined the mod relation, this
satisfies the desideratum for m < 0 too:
     7 mod -5 = -3     7 == -3 (mod -5)
    -7 mod -5 = -2    -7 == -2 (mod -5)
Python's % also produces these results.  (Another hint that this
is the Right Thing is that the identity
    0 <= (x mod m)/m < 1.
is preserved.  This doesn't hold with Numeric's % even for m > 0.)

That still leaves the question of zero as a right operand.  (Zero
as a left operand is no trouble at all, of course.)  From the
definition of the relation we have the cute fact that
    x == y (mod 0)   iff   x = y
The way to meet the desideratum in this case is to have
    x mod 0 = x
for all x.  This contradicts the definition
    x mod m   :=   x - m*floor(x/m)
since that would have x mod 0 undefined; and indeed Python's %
raises ZeroDivisionError here.  So Python's % is not *quite* mod
either; but an exception is probably more pragmatic for zero
modulus anyway.

-- 
Steven Taschuk                          staschuk at telusplanet.net
"Its force is immeasurable.  Even Computer cannot determine it."
                           -- _Space: 1999_ episode "Black Sun"