[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: sebastian.egner@xxxxxxxxxxx, srfi-77@xxxxxxxxxxxxxxxxx*Subject*: Re: Integer residue-classes [was: Questions about srfi-77 Generic Arithmetic]*From*: William D Clinger <will@xxxxxxxxxxx>*Date*: Tue, 21 Feb 2006 10:56:05 -0500*Cc*: lucier@xxxxxxxxxxxxxxx, will@xxxxxxxxxxx*Delivered-to*: srfi-77@xxxxxxxxxxxxxxxxx

> 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

- Prev by Date:
**Integer residue-classes [was: Questions about srfi-77 Generic Arithmetic]** - Next by Date:
**Re: Integer residue-classes [was: Questions about srfi-77 Generic Arithmetic]** - Previous by thread:
**Re: Integer residue-classes [was: Questions about srfi-77 Generic Arithmetic]** - Next by thread:
**Re: Integer residue-classes [was: Questions about srfi-77 Generic Arithmetic]** - Index(es):