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.

This posting is for documenting the rationale of the design
for DIV and MOD we proposed in Egner et al. (Scheme Workshop
2004), an article discussing number types in Scheme.
As far as I know, the definition of DIV and MOD given there
is new. Of course this makes it an experimental design,
and will not be the most widely used. Nevertheless, I am
convinced that the DIV and MOD functions we propose are
exactly the right thing to define for a general purpose
programming language. Moreover, I am convinced that it makes
all other conventions, in particular R5RS's QUOTIENT,
MODULO and REMAINDER, obsolete---except maybe for backwards
compatibility in case the following definitions are too
much to ask for:

(define (quotient n1 n2)
  (if (zero? n2)
      (error "undefined")
      (* (sign n1) (sign n2) (div (abs n1) (abs n2)))))

(define (remainder n1 n2)
  (if (zero? n2)
      (error "undefined")
      (* (sign n1) (mod (abs n1) (abs n2)))))

(define (modulo n1 n2)
  (if (zero? n2)
      (error "undefined")
      (* (sign n2) (mod (* (sign n2) n1) (abs n2)))))

In Egner et al. the only rationale presented for DIV/MOD
is in the context of the main theme of the article: Design
of number types. The advantage is offered that DIV and MOD can
be used 'off the shelf' for constructing arbitrary signed and
unsigned finite-precision integer types. But there is more,
and this posting is an attempt to provide substance to my
claims that DIV and MOD as defined in Egner et al. are the
right thing to have in the language.

I will first recap a few basic algebraic facts, in the
terminology of the Mathworld dictionary.

Facts about the integers: Residue-class rings
---------------------------------------------

1. The set Z of integers, together with the usual addition
and multiplication operation, has the following structure:
a) (Z, +, *) is a ring.
   http://mathworld.wolfram.com/Ring.html
b) The ring Z is an integral domain.
   http://mathworld.wolfram.com/IntegralDomain.html
      This means if a product is zero at least one of the
   factors is zero.
c) The integral domain Z is even a principal ideal domain (PID).
   http://mathworld.wolfram.com/PrincipalIdealDomain.html
      This effectively means that any equivalence relation on the
    integers compatible with its ring structure is of the form
      x ~ y <=> m divides (x - y),
   for some fixed integer m. Here, m = 0 should be interpreted
   as x ~ y <=> x = y for reasons that will become clear later.

An ideal of Z is a non-empty subset of Z which is closed
under addition and under multiplication with any element of Z.
   http://mathworld.wolfram.com/Ideal.html

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.

2. The important thing about ideals is that they define quotient
rings (which are even fields if m is prime): For integer m,

  Z/(m*Z) = { {x + m*k : k in Z} : x in Z }

is itself a ring with addition and multiplication defined as

  {x + m*k : k in Z} + {y + m*k : k in Z} = { (x+y) + m*k : k in Z}
  {x + m*k : k in Z} * {y + m*k : k in Z} = { (x*y) + m*k : k in Z}.

(At this point it is usually proved that these definitions are
indeed well defined, and that the resulting structure is a ring.
But this is not a lecture in algebra, so I skip it.)

The ring Z/m*Z is called 'quotient ring' or 'residue-class ring,'
its elements are called 'residue-classes.'
   http://mathworld.wolfram.com/QuotientRing.html

The quotient ring Z/m*Z is related to the base ring Z by the
function x -> x + m*Z, mapping Z into Z/m*Z. This function is
called 'natural projection'. As we will see it is related to
a 'mod'-like feature.
   http://mathworld.wolfram.com/NaturalProjection.html

3. The last concept necessary to understand what is going
on with div/mod (or quotient, remainder, modulo... you name
it) is the notion of 'system of representatives'.
   http://mathworld.wolfram.com/ClassRepresentative.html
   (The equivalence relation is x ~ y <=> m divides (x - y).)
   http://mathworld.wolfram.com/RightTransversal.html
   (The group G is (Z, +); the subgroup H is (m*Z, +).)

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.
Such a selection, i.e. a subset of the integers containing
exactly one element per residue class modulo m, is called
a 'system of representatives' (more precisely: a minimal
complete system of representatives), or SOR for short.

Mathematically, all SORs are equal:
{340, 744, 911} is as good for working in Z/3*Z as {0,1,2},
e.g. (340 + 3*Z) + (911 + 3*Z)= (744 + 3*Z).

Programming with residue-class rings
------------------------------------

For the purpose of programming, however, two SORs are much
more equal than all the others:
a) Representatives of minimal non-negative value.
b) Representatives of minimal absolute value, breaking ties
   such that there is one more negative value.

Spelling out the details of the two preferred SORs:
* Z/0*Z: SOR a) = SOR b) = Z = {..., -2, -1, 0, 1, 2, ...}
* Z/1*Z: SOR a) = SOR b) = {0}
* Z/m*Z for m >= 2, m even:
    SOR a) {0..m-1}
    SOR b) {-m/2..m/2-1}
* Z/m*Z for m >= 3, m odd:
     SOR a) {0..m-1}
     SOR b) {-(m-1)/2..(m-1)/2}
* Z/m*Z for m < 0: exactly the same as Z/((-m)*Z).

SORs a) and b) are preferred because efficient algorithms
are known (e.g. Euclid's) for computing the representatives
of minimal value, the 'canonical representative.'
   http://mathworld.wolfram.com/EuclideanRing.html

4. In Scheme (or any other non-computer-algebra programming
language) we do not want to work with the residue-classes
themselves, i.e. with subsets of integers. Instead, we prefer
to work with representatives, only. (This wish is the source
of all confusion, and 'ad hoc'ity.)

For this reason, there are 'DIV'- and 'MOD'-like procedures
mapping integers into integers, and possibly exceptions.
The purpose of (x mod m) is computing a canonical representative
of the residue-class (x + m*Z) in Z/m*Z, with respect to some
implicitly defined system of representatives. The purpose
of (x div m) is computing the associated multiple of m,
such that x -> (x div m, x mod m) is one-to-one (bijective).
In other words, the 'DIV'-like feature computes an element
of the ideal defining the quotient ring, or rather some
integer (x div m) representing the ideal-element (x div m)*m.

5. The "trick" presented in Egner et al. is using the sign of
m for selecting one of the preferred systems of representatives.
This is possible because the sign of m has no algebraic
relevance whatsoever for the residue class ring Z/(m*Z).
Of course there is no mathematical need for using the sign
of the modulus in this way---and in this sense this choice
is 'ad hoc.' But it turns out to be useful.

Filling in the details, we define div and mod be the
following properties: For all integer x and m,
(1) x = (x div m)* m + (x mod m),
(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
(3) (x div m) is integer.

An alternative to the "trick" would be providing two
separate sets of DIV/MOD operations: one 'unsigned' and
one 'signed', aka SOR a) and b). This makes the system
of representatives a static property of the program,
but I doubt that this is helpful in any way. The down
side is that there is no representation readily available
for the choice of system of representives.

As it happens, I had written a library for elementary
number theory. It turned out that DIV and MOD are exactly
the operations needed. This is no coincidence because they
were designed to be---after I had to track down too many
bugs originating from QUOTIENT/REMAINDER/MODULO.

Design principles of DIV/MOD
----------------------------

The operations DIV and MOD proposed in Egner et al.
are based on the following principles:

#1: The algebraic ring structure of the integers is
transported into the residue-class ring. In other words,

  (mod (+ x y) m)  equals  (mod (+ (mod x m) (mod y m)) m)
  (mod (* x y) m)  equals  (mod (* (mod x m) (mod y m)) m)

for all integer x, y and m.

#2: DIV and MOD are associated to each other. In other words,

  (+ (* (div x m) m) (mod x m))  equals  x

for all integer x, m.

#3: The system of representatives can be selected easily
(using the sign of the modulus m) and comprehensible:
Either minimal non-negative values, all integers, or
minimal absolute values.

The design of QUOTIENT/REMAINDER/MODULO
---------------------------------------

Brad wrote:
> (a) I think it is a really bad design to have the basic
> operation of div+mod change when the second argument
> changes sign.

The bad design here is that *neither* QUOTIENT/REMAINDER
nor QUOTIENT/MODULO form a consistent pair of residue-class
operations: QUOTIENT and REMAINDER are associated, but
REMAINDER does not transport the ring structure (Example 1).
MODULO does transport the ring structure but is not
associated with QUOTIENT (Example 2) or any other procedure
available in R5RS.

Example 1:
(= (remainder (+ 1 -3) 3)
   (remainder (+ (remainder 1 3) (remainder -3 3)) 3)) => #f

Example 2:
(= (+ (* (quotient -1 3) 3) (modulo -1 3)) -1) => #f

Moreover, in R5RS the system of representatives is specified
implicitly by some relations between the signs of arguments
and of values in what I would call 'totally ad hoc' way.
In practice, when there is any chance of a negative argument
I fall back on trying examples to make sure the result is
what I need. DIV and MOD have removed this habit.

The zero modulus case
---------------------

Will wrote:
> Brad wrote:
> >    (b) I think it is a really bad design to have
> >        (div x1 0) => 0
> > It conflicts with the requirement in quotient+remainder,
> > quotient, remainder, and modulo that "n2 should be nonzero".
> > (Unless I read "should" here in the language lawyer sense,
> > i.e., that it is totally nonprescriptive.) The only way I can
> > think of making division by exact 0 make sense is by divorcing
> > the meaning of "div" from any notion of mathematical division.
>
> I don't have a strong opinion about this.  It is totally
> ad hoc, but the alternative is a principled (not ad hoc)
> hole in the domain of div.  I'm inclined to think that
> passing 0 as the second argument to div is, in practice,
> most likely an error for which it would be more useful
> to signal an error than to return 0, but I'm willing to
> listen to an argument for returning 0.  So far as I can
> see, no such argument has been made.  In particular, the
> paper by Egner et al contains no such argument.

The definition (div x 0) => 0 is perfectly natural. It is
based on the fact that 0*Z = {0} is an ideal in Z, and so
there is a quotient ring R = Z/(0*Z), which happens to be
isomorphic to Z itself because x + 0*Z = y + 0*Z iff x = y.
Hence, working with representatives, (mod x 0) must be x
for all x---and #2 implies (div x 0) => 0. It looks funny,
but you get used to it quickly.

In effect, design principles #1 and #2 (and #3) are valid
for all values of the modulus, including zero.

Brad's reflex of interpreting "(div x 0) => 0" as 'division
by zero' only means that he confuses residue-class operation
'div' with the *field* operation '/'. (For which, by the way,
division by [inexact] zero is not seen as much of a problem,
even though in this case no algebraically consistent way of
defining it exists; 1/0 := inf is just postponing the error.)

Summarizing, (Brad) "It conflicts with the requirement in
[...] modulo that 'n2 should be nonzero.'" is correct,
except that the conflict exists because the requirement
in R5RS is arbitrary in the first place---a result of the
'ad hoc' definition of QUOTIENT, REMAINDER and MODULO.

The residue-class constructing operation 'div' should not
be confused with the field operation '/', which is the
inverse of multiplication in a field. And to make life even
more complicated, neither 'div' nor '/' should be confused
with 'modular division', i.e. the inverse operation of
multiplication in the residue-class ring Z/m*Z (which comes
down to an extended gcd computation).

Generalization to non-integer arguments
---------------------------------------

The definition of DIV and MOD implies the following property:

x div m = floor(x/m)      if m > 0
        | 0               if m = 0
        | ceil(x/m - 1/2) if m < 0.

Taking this property as a definition of div, and defining
x mod m = m - (x div m)*m to satisfy (1), we obtain div/mod
that are meaningful for all real numbers x and m.

As it turns out (not entirely coincidental), design
principles #1, #2 and #3 still hold in the generalization.

The generalization of div/mod defined above is not based
on quotient rings, because these are boring if the base
ring is a field.

The generalization above is based on equivalence:
Defining x ~ y as (x mod m) = (y mod m) for m != 0 means
x - y is an integer multiple of m, even for non-integer m.
Such a structure is the 1-dimensional special case of a
'lattice', i.e. a Z-module embedded in a real vector space
(and the famous LLL-algorithm computes a pretty base.)

The generalized DIV/MOD can be useful with bignum rationals
and floats, as in sin(x) = sin(x mod (2 pi)), but not many
programs really require the 1-dim. lattice reduction in my
experience. On the other hand, the generalization hardly ever
gets in the way of the integer functionality that matters.

Sebastian