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

*To*: srfi-77@xxxxxxxxxxxxxxxxx*Subject*: Re: div0 and mod0*From*: William D Clinger <will@xxxxxxxxxxx>*Date*: Mon, 14 Aug 2006 16:50:31 -0400*Cc*: lucier@xxxxxxxxxxxxxxx*Delivered-to*: srfi-77@xxxxxxxxxxxxxxxxx

I apologize for overlooking Brad's message of 25 July on the subject of "div0 and mod0". Brad Lucier wrote: > div0 and mod0 > > 3. are useful in no algorithms of which I am aware; The current revision of the reference implementation for SRFI 77 contains the following uses of div0 and mod0. (I have edited this to remove some debugging code that would be removed in the next major version anyway.) Similar uses of div0 and mod0 are found in the definition of fixnum*/carry, and similar uses will be found in a more efficient version of the bignum code if I ever get around to writing it. ; The challenge of fixnum*/2 is to avoid overflow when ; computing the intermediate results. That is done here ; by computing modulo 1/2 the usual modulus, which this ; code assumes to be an even power of two. ; ; (a * m + b) * (c * m + d) ; = (a * c) * m^2 + (a * d + b * c) * m + b * d (define (fixnum*/2 x y) (call-with-values (lambda () (fixnum-div0+mod0 x *half-modulus*)) (lambda (a b) (call-with-values (lambda () (fixnum-div0+mod0 y *half-modulus*)) (lambda (c d) (let* ((a*d (r5rs:* a d)) (b*c (r5rs:* b c)) (b*d (r5rs:* b d)) (a*d+b*c (fixnum+/2 a*d b*c)) (hibits (fixnum-mod a*d+b*c *half-modulus*)) (hibits (if (fixnum>? hibits *half-high*) (fixnum- hibits *half-modulus*) hibits)) (hi (r5rs:* hibits *half-modulus*)) (lo b*d)) (fixnum+/2 hi lo))))))) > Yet quotient and remainder have been removed by this > SRFI, with the only rationale being: > > Well, no rationale is given, only the bald statement > > > The quotient, remainder, and modulo procedures were removed. > > > This behavior might be characterized as "program > language design by assertion". Part of the rationale for removing remainder runs something like this: For any modulus n2, we would like to project arbitrary integers onto a set of n2 distinguished representatives of Z/n2. The R5RS remainder procedure does not do this: it projects onto a set of 2*n2-1 representatives. The mod, mod0, and R5RS modulo procedures all project onto a set of n2-1 representatives, but the sets are different: mod: { 0, 1, ..., |n2| - 1 } mod0: { - |n2|/2, ..., |n2|/2 - 1 } if n2 is even { - (|n2|-1)/2 , ..., (|n2|-1)/2 } if n2 is odd modulo: { - n2 + 1, ..., 0 } if n2 is negative { 0, ..., n2 - 1 } if n2 is positive With mod, the representatives are non-negative, which is advantageous when projecting to an index into Scheme's 0-origin structures (vectors, strings). With mod0, the representatives are centered (or nearly so) about zero, which is advantageous when working with two's complement, which shows up in R6RS fixnum arithmetic and in R6RS bytes objects. With modulo, the representatives have the sign of the divisor. Although a lot of hardware works this way, and many programming languages work this way, I don't know of use cases where this is really what you want. Since the modulo procedure was an orphan in the R5RS, without any matching division operator, the choice was between adding a division operator that plays well with modulo, or to remove modulo. Not knowing of any use cases for modulo that are as compelling as those for mod and mod0, we left it out. > I think these two decisions should be reversed and a > division operator associated with the existing modulo in > RNRS be added. I expect the quotient, remainder, and modulo procedures to be provided by an R5RS-compatibility library. I believe that to be the right place for them if the primary argument for keeping them is backward compatibility with R5RS and earlier. Bear, Marcin Kowalczyk (citing Knuth, but Knuth's argument as cited doesn't hold for negative divisors, so Knuth seems to be neutral between mod and modulo), and Brad Lucier have all argued for modulo and a matching division operator (absent from R5RS), but none have yet cited applications for which modulo works better than mod. I'd like to see examples. Bear and Kowalczyk, citing Knuth, have argued against quotient/remainder on the grounds I gave above, while Egner et al gave another argument against remainder. Kowalczyk and Lucier have cited the hardware-friendliness of quotient/remainder, but I don't regard that by itself as an advantage; I'd like to see examples for which the quotient/remainder behavior is what you'd actually want, as opposed to the div/mod or div0/mod0 behavior. Will

**Follow-Ups**:**Re: div0 and mod0***From:*Bradley Lucier

- Prev by Date:
**Re: fixnum-* operations** - Next by Date:
**Re: div0 and mod0** - Previous by thread:
**div0 and mod0** - Next by thread:
**Re: div0 and mod0** - Index(es):