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.modulo

plus 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