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

Re: arithmetic issues



   Date: Fri, 21 Oct 2005 10:53:26 -0400 (EDT)
   From: Aubrey Jaffer <agj@xxxxxxxxxxxx>

   Its time to move beyond the machine-language mindset.  I code in
   Scheme because I want a high-level language.

I very strongly agree with this.  On that note, I'd like to suggest a
somewhat different alternative from what many people have been
suggesting here: I'm ambivalent about exactness and mathematical
accuracy of the general operations provided, but I think high-level
numerical operations should be provided nevertheless, with all general
argument dispatching &c.  Indeed, it might even be useful to allow
extensions like what scmutils provides to allow passing functions to
operators like +.  Provided with user declarations/proclamations that
certain quantities will be valid array or vector indices, for which I
think a syntax ought to be standardized, the problem of flow analysis
to elide numerical dispatch on these indices is reduced dramatically,
and there is no longer any need for an arbitrary 'fixnum' range, which
is less specific anyway than that of array or vector indices.

The notion of 'fixnum' and 'flonum' is an implementation detail; it
should really not be exposed to the user, as this simply shows a
weakness in the expressiveness of the language.  What is needed,
though, is a method of specifying modular or inexact arithmetic more
precisely than the vague fixnum and flonum mechanism.  Many
applications work with 32-bit or 64-bit modular integer arithmetic,
such as cryptographic applications.  Many other applications require
operations on IEEE floating point numbers, and for these operators
should be provided _specifically_ for IEEE floating point operations;
e.g., IEEE-FLO32+ or IEEE-FLO64-EXPT, &c.  These are not performance
considerations, but necessary for the correct semantics of many
applications.  Additionally to arithmetic routines, binary decoding
and encoding of IEEE floats should be provided, probably on SRFI 74
blobs.

I'm not sure what the best way to specify general modular arithmetic
is, but I imagine something like a MODULAR-ADDER, MODULAR-SHIFTER,
&c., could be defined; e.g.,

  ((modular-adder 32) 123 456)               => 579
  ((modular-adder 32) (- (expt 2 32) 1) 1)   => 0
  ((modular-shifter 32) 3 13)                => 24576
  ((modular-shifter 32) 1 32)                => 0

With constant operands, these can be optimized trivially to machine
addition, and they conduce flow analysis needed to store integer
quantities in 32-bit scratch registers -- wider than most Scheme
systems can provide with tagged fixnums.  A convenient syntax might be
added on top of this, such as:

  (with-modular-arithmetic 32 (+ arithmetic-shift)
    (+ 1 (bitwise-not (arithmetic-shift -1 32))))
    => 0
  
(The first operand specifies the modulus; the second, a list of names
to be bound to appropriate arithmetic operations.  I'm not entirely
sure whether this is the right kind of syntax, but it is one
possibility.)