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

Re: inexactness vs. exactness



 | From: William D Clinger <will@xxxxxxxxxxx>
 | Date: Wed, 27 Jul 2005 08:48:36 +0200
 | 
 | Aubrey Jaffer wrote:
 | > But if we consider memory limitations for this system, then there
 | > are many mathematical numbers between any two representable
 | > inexacts whose storage requirements are too large to be
 | > represented on a particular physical computer.
 | 
 | This is true of exact rationals as well.  It is the programmer's
 | responsibility to limit the precision of the program's numbers so
 | the computer doesn't run out of memory.  One of the advantages of
 | floating point representations for inexact numbers is that they do
 | this automatically; one of the disadvantages of R5RS inexact
 | arithmetic is that it doesn't guarantee such limited precision.

My current thinking is to modify SRFI-70 to incorporate this
distinction between exact and inexact:

* A number is exact if it was written as an exact constant or was
  derived from exact numbers using only exact operations.

  The procedures listed below will always return an exact result
  provided all their arguments are exact and the mathematically
  expected result is representable as an exact number within the
  implementation.

     +            -             *
     quotient     remainder     modulo
     max          min           abs
     numerator    denominator   gcd
     lcm          floor         ceiling
     truncate     round         rationalize
     expt         floor->exact  ceiling->exact
     truncate->exact            round->exact

  For exact numbers, it is the programmer's responsibility to avoid
  using numbers with magnitude or precision too large to be
  represented in the implementation.

* A number is inexact if it was written as an inexact constant, if it
  was derived using inexact ingredients, or if it was derived using
  inexact operations.  Thus inexactness is a contagious property of a
  number.

  Inexact numbers are approximate.  Every mathematical number within
  the (convex) range of inexacts supported by an implementation will
  round to an inexact number on input or as a result of computation.
  The neighborhood of mathematical numbers rounding to a particular
  inexact number must be simply connected.

  In an implemenation supporting inexact numbers, all mathematical
  real numbers will round to inexact real numbers on input or as a
  result of a computation.

  For complex numbers, it is the programmer's responsibility to avoid
  using numbers with magnitude too large to be represented in the
  implementation.

  It is the duty of each implementation to make the result of
  mathematical expressions as close as practical to the mathematically
  ideal result.  The error in results of optimized or compiled
  mathematical expressions must be no larger than the error band
  expected from the combination of the error bands of its component
  operations.

Note that while the whole real line is covered by the neighborhoods
associated with inexact reals, there may be many mathematical numbers
which equal no exact number in an implementation.

The programmer's responsibility to avoid using exact numbers with
overlarge precisions conflicts with the practice of using series and
iteration to approximate mathematical functions.  The higher order
terms providing accuracy are harmless to inexact numbers, but can
cause precision to explode in exact representations.

Everyday inexact flonum computations like matrix triangulation,
statistical analysis, or discreet Fourier transforms combine hundreds
of inexact numbers.  Such code is unlikely to have been crafted to
limit the intermediate precision swell which would result if it was
run as exacts such as exact-rational or computable-real.

In SRFI-70, computable-reals must be exact because determining the
closeness of two numbers (for the purpose of inexact rounding) is not
necessarily decidable.  This difficulty with comparisons extends to <,
<=, =, >, >=, NEGATIVE?, POSITIVE?, and ZERO?.

Making comparisons with computable-reals inexact might give more
flexibility in dealing with them.  But, as expressed earlier, programs
doing floating-point data crunching seem unlikely to run successfully
in a computable-real implementation.  Dropping the program into the
undecidable abyss when it tries to compare a computable-real number is
not useful.  Comparisons of computable-reals must be carefully
planned; they should be specialized operators.

Inexact rational numbers pose no problem so long as the precision of
results is bounded.  W. Clinger suggests limiting the precision of the
result to the precision of the most precise argument.