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

This page is part of the web mail archives of SRFI 77 from before July 7th, 2015. The new archives for SRFI 77 contain all messages, not just those from before July 7th, 2015.

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