[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
# Integer residue-classes [was: Questions about srfi-77 Generic Arithmetic]

`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`