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

arithmetic issues

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.



 | Members of the Scheme community are encouraged to express themselves
 | on the following issues:

 | * Instead of requiring the full numeric tower, R6RS could require
 |   only the fixnum/flonum base, and make the full tower available
 |   as modules in the standard library.

SCM has compile-time conditionals which enable bignums, flonums, and
complex flonums.  This selectivity has been used to port SCM and JACAL
to small platforms like the Pocket-PC.

SCM's primary target application is JACAL, a symbolic math system.
JACAL does not use inexact numbers.  I am open to mandating bignums.
Flonums often are the most difficult feature to port to new
architectures.  But computer science is a half-centry old already --
tiny implementations can say they implement a subset of R6RS.

If fixnums and flonums are the minimum tower, then "/" of fixnums
(which don't divide evenly) should be required to return the closest
flonum.

 | * The main problem with banishing the full tower to a library is
 |   that read, write, and several other procedures must know about
 |   the external representations of all numbers.

For an interpreter this would mean that 1/2 read before the full-tower
module was loaded could be an inexact 0.5; but after loading 1/2 would
read as an exact 1/2.  Unpredictability is bad.

 | * Should a minimum precision be required for fixnums or flonums?

The Common-Lisp specification
<http://www.cs.cmu.edu/Groups/AI/html/hyperspec/HyperSpec/Body/convar_most-p_ative-fixnum.html>
mandates a fixnum precision of at least 16.bit:

  MOST-POSITIVE-FIXNUM, MOST-NEGATIVE-FIXNUM

  Constant Value:

  implementation-dependent.

  Description:

  most-positive-fixnum is that fixnum closest in value to positive
  infinity provided by the implementation, and greater than or equal
  to both 2^15 - 1 and array-dimension-limit.

  most-negative-fixnum is that fixnum closest in value to negative
  infinity provided by the implementation, and less than or equal to
  -2^15.

I recommend 12.bits minimum precision for both fixnums and flonums.

 | * Should the range of a fixnum be restricted to a power of two? To
 |   a two's complement range?

No strong preferences.

Both Common-Lisp and SLIB implement MOST-POSITIVE-FIXNUM and
MOST-NEGATIVE-FIXNUM, which would be good additions to R6RS.

 | * The fixnum operations provide efficient fixnums that "wrap."
 |   However, they do not give efficient access to the hardware
 |   facilities for carry and overflow. This would be desirable to
 |   implement efficient generic arithmetic on fixnums portably. On
 |   the other hand, there isn't much experience with formulating a
 |   portable interface to these facilities.

In well-written interpreted implementations, fixnum operations would
provide no speed increase.  SCM's type dispatch for immediate numbers
is just 3 instructions: mask, test, and conditional jump.  With modern
processors executing scores of instructions in the time it takes for a
single cache line to be retrieved from memory, most data type
dispatches use time which would otherwise be spent waiting for program
or data caches.

The same would hold true for many nontrivial compiled Scheme programs.

 | * The fixnum operators wrap on overflow, i.e., they perform modular
 |   arithmetic.  For many purposes, it would be better for them to
 |   signal an error in safe mode.  Since the modulus is
 |   implementation-dependent, portable code cannot generally take
 |   advantage of the wrapping.  Instead, applications are likely to
 |   use fixnums simply to avoid the overhead of generic arithmetic
 |   under the assumption that all quantities computed fit in the
 |   fixnum range, and feedback if this turns out not to be the case
 |   will be valuable.  On the other hand, the wrapping semantics can
 |   also be useful, i.e., in the coding of a practical implementation
 |   of bignums in terms of fixnums.  It may be that we should
 |   consider including two sets of operators: fx operators that
 |   signal an error upon overflow and wfx operators that wrap.

SCM has real-only operations like $log and $sin, which I never use;
even though I do substantial floating point computing.  In most
nontrivial computations, a couple percent speed improvement from
fiddling with the minutia of low-level procedures is dwarfed by the
speed improvements netted by memoizing the results of certain
sub-calculations or vectorizing computations in SRFI-63 uniform
arrays.

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

 | * Should the binary fixnum/flonum operations allow other than two
 |   arguments?

Yes; because these operations are pointless for interpreters, and
variable arity invokes no penalty in compiled code.

 | * What are the semantics of "safe mode" and "unsafe mode"?  (This
 |   is a much larger question that R6RS should address.)

Global modes destroy modularity.  In a compiled implementation, the
assumption that safe and unsafe compiled modules could be linked
together is unwarranted.

 | * Should R6RS allow other inexact reals beside the flonums?  This
 |   draft does allow them, at the cost of some complications and
 |   additions such as real->flonum.  (See the Design Rationale.)

+inf.0, -inf.0, and NaNs should be inexacts.

 | * Should the R5RS procedures for generic arithmetic (e.g. +)
 |   remain in R6RS?  Here are five possible answers, phrased in terms
 |   of the + procedure:

 |      1. + is not defined in R6RS.

 |      2. + is defined to be a synonym for the ex+, so its domain is
 | 	restricted to exact arguments, and always returns an exact
 | 	result.

 |      3. + is defined as the union of the ex+ and in+ procedures,
 | 	so all of its arguments are required to have the same
 | 	exactness, and the exactness of its result is the same as
 | 	the exactness of its arguments.

 |      4. + is defined as in R5RS, but with the increased
 | 	portability provided by requiring the full numeric
 | 	tower.  This alternative is described in the section
 | 	R5RS-style Generic Arithmetic.

 |      5. + is defined to return an exact result in all cases, even
 | 	if one or more of its arguments is inexact.  This
 | 	alternative is described in the section Generic Exact
 | 	Arithmetic.

 |   Will Clinger prefers the 4th possibility, Mike Sperber the 5th.

I want a sixth option:

     6. + is defined as in R5RS (and SRFI-70).

 | * If R6RS does not adopt a R5RS-style model for the generic
 |   arithmetic, should it still provide more R5RS-compatible generic
 |   arithmetic as a library?

Replacing the numeric subsystem including uniform arrays would change
too many procedures; we are then talking about two languages.

 | * The external representations of 0.0, -0.0, infinities and NaNs
 |   must be specified.  The notations used here are used by several
 |   other languages, and have been adopted by several
 |   implementations of Scheme, but other notations are possible.

Adding syntax for infinities is good.

Being error objects, syntax for NaNs should be unspecified.

None of the examples in SRFI-77 return -0.0 unless they are passed
-0.0 as an argument.  Does -0.0 result only from a literal -0.0
constant?

In an implementation with -0.0, what is the result of (* -5.0 0.0)?

-0.0 is insufficiently specified by SRFI-77; it will be a portability
killer.

 | * The fixnum, flonum, and inexact arithmetic come with a full deck
 |   of operations, including some that are defined in terms of
 |   integers (such as quotient+remainder, gcd and lcm), and others
 |   that are easily abused (such as fxabs).  Should these be pruned?

quotient+remainder introduces a new procedure naming convention which
doesn't play well with -.

The mathematical term for quotient with remainder is division; the
verb form being divide.  How about changing QUOTIENT+REMAINDER to
DIVIDE.

 | * The R5RS says this:

 |       Rationale: Magnitude is the same as abs for a real argument,
 |       but abs must be present in all implementations, whereas
 |       magnitude need only be present in implementations that
 |       support general complex numbers.

 |   Given that this SRFI suggests requiring all implementations to
 |   support the general complex numbers, should abs (and exabs and
 |   inabs) be removed?

No.  Absolute-value is a common name for the operation.

 | * The real?, rational?, and integer?  predicates must return false
 |   for complex numbers with an imaginary part of inexact zero, as
 |   non-realness is now contagious.  This causes possibly unexpected
 |   behavior: `(zero? 0+0.0i)' returns true despite `(integer?
 |   0+0.0i)' returning false.  Possibly, new predicates realistic?,
 |   rationalistic?, and integral?  should be added to say that a
 |   number can be coerced to the specified type (and back) without
 |   loss.  (See the Design Rationale.)

Mathematically, mixed exactness complex numbers makes no sense.
Twisting the whole numeric tower around this artifice is wrong.

If the goal is to make real inexacts and complex inexacts separate
types, then state it that way.  I am open to separating complex from
real; I am strongly opposed to mixed exactness.

 | * Most Scheme implementations represent an inexact complex number
 |   as a pair of two inexact reals, representing the real and
 |   imaginary parts of the number, respectively.  Should R6RS mandate
 |   the presence of such a representation (while allowing additional
 |   alternative representations), thus allowing it to more
 |   meaningfully discuss semantic issues such as branch cuts?

The procedures REAL-PART, IMAG-PART, and MAKE-RECTANGULAR already
guarantee that the orthogonal representation is available.  The
language should not constrain an internal representation which is
transparent to the user.

 | * The x|53 default for the mantissa width discriminates against
 |   implementations that default to unusually good representations,
 |   such as IEEE extended precision.  Are there any such
 |   implementations?  Do we expect such implementations in the near
 |   future?

Not that I know of.

 | * Should `(floor +inf.0)' return +inf.0 or signal an error
 |   instead?  (Similarly for ceiling, flfloor, infloor, etc.)

Floor is specified to return an integer.  +inf.0 is not an integer.
Thus it is an error.

 | * The bitwise operations operate on exact integers only.  Should
 |   they live in the section on exact arithmetic?  Should they carry
 |   ex prefixes?  Or should they be extended to work on inexact
 |   integers as well?

They should work on all exact integers.

Arithmetic-shift is not good as a low level operation on many CPUs.
For low level it should be split into left shift and right shift
procedures.