Re: Integer residue-classes [was: Questions about srfi-77 Generic Arithmetic]

[William D Clinger <will@xxxxxxxxxxx>]

> Will wrote:
> > Brad wrote:
> > > 8.  Integer Divison.
> > > (a) I think it is a really bad design to have the basic
> > > operation of div+mod change when the second argument changes sign.
> > 
> > I don't have much problem with that.  These mathematical
> > operations aren't defined at zero, so they have to compare
> > against zero anyway.  To quote Egner et al, "the sign of
> > the modulus y determines which system of representatives
> > of the residue class ring Z/yZ is being chosen, either
> > non-negative (y > 0), symmetric around zero (y < 0), or
> > the integers (y = 0)."  Using the sign of y is ad hoc,
> > but it's an ad hoc choice anyway.
> 
> No, it is not "ad hoc." It is based on the mathematics of 
> the integers---in the sense of elementary number theory, 
> not in the sense of Brad's "any notion of mathematical 
> division," whatever that may be.

Denying the ad hockitude doesn't make it go away.  The
background material you provided will help me to explain
how little is at stake here to those who are wondering
what this is about, and I thank you for that.  In my
opinion, your failure to understand Brad's objection,
and to recognize the ad hockitude even after two other
mathematicians have pointed it out, also provides some
persuasive evidence for Brad's contention that ordinary
Scheme programmers are likely to be confused by this
unless we fix it.

> Another way of saying c) is that every ideal is generated
> by a single element, which I denote by m, and is of the 
> form m*Z = {m*k : k in Z}. To spell it out, the ideals
> of the ring of integers are
>   0*Z = {0}
>   1*Z = (-1)*Z = Z = {..., -2, -1, 0, 1, 2, ...}
>   2*Z = (-2)*Z = {..., -6, -4, -2, 0, 2, 4, 6, ...}
>   3*Z = (-3)*Z = {..., -6, -3, 0, 3, 6, ...}
>   etc.

In particular, 3*Z=(-3)*Z.  A programmer would therefore
expect either (div 5 3) and (div 5 -3) to be equal, or
perhaps (mod 5 3) and (mod 5 -3) to be equal, or perhaps
even both.  In SRFI 77, however:

    (div 5 3)    ==>  1
    (div 5 -3)   ==>  -2

    (mod 5 3)    ==>  2
    (mod 5 -3)   ==>  -1

That is not just ad hoc, it is confusing.  Another way
to see that the definitions of div and mod in SRFI 77
are ad hoc is to observe that

> (2) if m > 0: 0   <= (x mod m) < m
>     if m = 0:        (x mod m) = x
>     if m < 0: m/2 <= (x mod m) < -m/2, and

could be changed to

 (2) if m < 0: 0   <= (x mod m) < m
     if m = 0:        (x mod m) = x
     if m > 0: m/2 <= (x mod m) < -m/2, and

while preserving all of the important mathematical properties
you claimed for div and mod.

> Since the residue classes x + m*Z = {x + m*k : k in Z} are
> pairwise disjoint, we can pick a representative element
> from each residue class and only work with representatives.

There are infinitely many ways we could choose represenatives
from those residue classes.  As you observe, however, two
particular choices of representatives are convenient for
programming:

> a) Representatives of minimal non-negative value.
> b) Representatives of minimal absolute value, breaking ties
>    such that there is one more negative value.

In defining div and mod for your paper at the Scheme workshop,
you made an ad hoc decision to select between these two based
on the sign of the second argument.  SRFI 77 just perpetuated
that ad hoc decision.  Now, "ad hoc" is not necessarily
pejorative in American mathematical English, so the fact that
it was an ad hoc decision does not necessarily imply it was
a bad one.

Before we commit to an ad hoc design, however, we should
compare it to a similar design that is not so ad hoc.
Consider, therefore, the following definitions of div, mod,
quo, and rem:

    (div q1 q2)                  ==> nd
    (mod q1 q2)                  ==> qm

    (quo q1 q2)                  ==> nq
    (rem q1 q2)                  ==> qr

where:

   1. q1 = nd * q2 + qm
   2. 0 <= qm < q2          if q2 <> 0
   3. q1 = nq * q2 + qr
   4. q2/2 <= qr < -q2/2    if q2 <> 0

With this definition,

    (div 5 3)    ==>  1
    (div 5 -3)   ==>  -1

    (mod 5 3)    ==>  2
    (mod 5 -3)   ==>  2

    (quo 5 3)    ==>  2
    (quo 5 -3)   ==>  -2

    (rem 5 3)    ==>  -1
    (rem 5 -3)   ==>  -1

To make these procedures as similar as possible to the div
and mod of SRFI 77, let nd=nq=0 and qm=qr=q1 when q2=0.

I claim that div, mod, quo, and rem have all of the desired
properties claimed for SRFI 77's div and mod, but without
the ad hoc choice of representative based on the sign of the
second argument.

I believe that div, mod, quo, and rem as defined in this
message would answer Dr Lucier's objection, except perhaps
for the case in which q2=0.

I therefore raise this as an issue:  Should we choose the
representatives based on the sign of the second argument,
as in Egner et al and in SRFI 77, or should we redefine
div and mod to choose the representatives consistently in
all cases, and define a second pair of procedures that use
the second most important choice of representatives?

Will