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.
On Aug 14, 2006, at 4:50 PM, William D Clinger wrote:
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)))))))
Will:You chose to illustrate the utility of fixnum-div0+mod0 by pointing to a routine in a runtime library. That, and your comment that "The challenge of fixnum*/2 is to avoid overflow," which, on its face, seems a bit extreme (avoiding overflow is *the* challenge?) reminded me of the following.
My experience in building runtime libraries (little that it is---I wrote the final set of elementary function routines for UCSD Pascal and then worked with Marc Feeley on the arithmetic runtime of Gambit) is that the constraints one is given and the design choices that one makes are often unusual to the point of being unique. For example, in UCSD Pascal the virtual machine would stop with an exception whenever a floating-point underflow-to-zero occurred. This made it imperative that my library avoid all underflows; perhaps one might say that avoiding underflow was *the* challenge, though I would think that the true challenge was to get a reasonable amount of accuracy for arguments over close to the maximum possible range within a reasonable execution time. At the time I had a prepublication copy of Cody and Waite; I was able to suggest some changes to the draft based on my somewhat unusual constraints, and several of these changes were incorporated (although the algorithm in the published text for exp, which I didn't get to until just before publication, would still underflow in double precision on the VAX).
Since you say so, I believe that the challenge, given your constraints, is to avoid overflow, but I don't know why. For example, in the Gambit Virtual Machine (GVM) it is assumed that signed multiplication "wraps", in the terminology of GCC, and the Gambit runtime takes advantage of that fact, and uses the -fwrapv flag with gcc to ensure it.
Your routine also assumes the availability of r5rs:*, but not, presumably, r5rs:modulus; that fixnum-div0+mod0 was written before, and not needing, fixnum*/2; and that you'd prefer to manipulate bit fields (which I presume you're doing, since I presume that *half- modulus*, etc., are powers of two) using fixnum-div0+mod0 instead of using shifts and logical operations, etc.
As these constraints seem to me very artificial, I do not find this application of, or need for, fixnum-div0+mod0 compelling.
Since you brought up runtime libraries, I decided to say what low- level fixnum routines are used in the runtime libraries for Gambit.
(##fixnum.+ x y) (adds with wrapping on overflow) (##fixnum.+? x y) (returns x+y if it's a fixnum, or #f otherwise) (##fixnum.* x y) (returns wrapped version of x*y)(##fixnum.*? x y) (if y is not 0 or -1, returns x*y if it is a fixnum, or #f otherwise)
(##fixnum.- x y) (returns wrapped version of x-y) (##fixnum.-? x y) (returns x-y if it's a fixnum, or #f otherwise)(##fixnum.-? x) (returns -x if x is not the most negative fixnum, #f otherwise)
##fixnum.quotient ##fixnum.remainder ##fixnum.moduloplus some unchecked versions of bitwise shifts of various types, and other operations that do not differ in principle from their generic counterparts except that they can be specialized for fixnums: max, min, zero?, <, ...
(##fixnum.*? x y) calculates (temp = x*y, (temp/y=x ? temp : #f))which is a correct test for overflow in multiplication if overflow wraps and y is not 0 or -1 (there are those constraints again!) and full multiplication of fixnums (which can be inlined if necessary) is
(cond ((##fixnum.= y 0)
0)
((if (##fixnum.= y -1)
(##fixnum.-? x)
(##fixnum.*? x y))
=> (lambda (result) result))
(else
(##bignum.* (##bignum.<-fixnum x) (##bignum.<-fixnum y))))
If you like, I can argue that *these* operations be included in R6RS,
and can offer the Gambit runtime as evidence that these operations
are useful.
But I don't intend to do that. Brad