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

Re: inexactness vs. exactness



 | Date: Mon, 18 Jul 2005 19:31:25 -0700 (PDT)
 | From: bear <bear@xxxxxxxxx>
 | 
 | On Mon, 18 Jul 2005, Aubrey Jaffer wrote:
 | 
 | > | Date: Mon, 18 Jul 2005 08:50:50 -0700 (PDT)
 | > | From: bear <bear@xxxxxxxxx>
 | > |
 | > | This draft effectively eliminates certain properties of
 | > | inexactness vs. exactness,
 | >
 | >SRFI-70 sharpens the distinction between inexacts and exacts.
 | 
 | It requires inexact numbers in many situations where exact
 | numbers can be produced.
 | 
 | >From
 | >the R5RS notation of inexacts it deduces their nature as real
 | >neighborhoods.
 | 
 | A point on which we disagree.  I don't think any such nature
 | was inherent in R5RS.

You are suggesting that an implementation in which inexact numbers are
not neighborhoods can conform to R5RS.  I will show that this is
impossible.

If real inexacts are not neighborhoods, then they correspond to single
mathematical numbers (points).

The number of inexact numbers possible in this hypothetical system is
either finite or not.

Finite number of inexacts:

  There are an infinite number of possible continuous formulas (Scheme
  procedures) yielding distinct values when applied to inexact
  arguments.  If the number of possible inexact numbers is finite,
  then an infinite number of the formula results must map to the
  finite inexacts; and (because of continuity) they must be
  neighborhoods.

Infinite number of inexacts:

  There are an infinite number of possible formulas (Scheme
  procedures) involving transcendental functions yielding distinct
  values when applied to inexact arguments.

    R5RS 6.2.2 Exactness states:

    If two implementations produce exact results for a computation
    that did not involve inexact intermediate results, the two
    ultimate results will be mathematically equivalent.  This is
    generally not true of computations involving inexact numbers since
    approximate methods such as floating point arithmetic may be used,
=>  but it is the duty of each implementation to make the result as
=>  close as practical to the mathematically ideal result.

  By R5RS 6.2.2, if a transcendental function returns an approximate
  result, then it must map to the nearest inexact number.  Thus
  inexacts designate their closest neighborhoods.

  Otherwise, the results of transcendental functions must not
  approximate; they must be mathematically correct.  But formulas
  yielding the same mathematical result must return inexact numbers
  which are `='.  Because those formulas include

    (log 2), (* 4 (atan 1)) [pi], exp, and sin,

  the equality between the results of two formulas is undecidable
  by a theorem of Richardson [Richardson1968].

So, not only is it proved that:

* Scheme inexact real numbers correspond to real neighborhoods;

applying the same logic to exact numbers proves that:

* it is not possible to create a real number representation with total
  order (comparisons) which is exact for all transcendental functions.

 | > Because exact numbers in Scheme designate single mathematical
 | > numbers, the idea of exactness as a superficial attribute of
 | > numbers must be jettisoned.
 | 
 | A conclusion based on the point on which we disagree. ...

The proof above makes this no longer a matter of opinion.

 | >  Inexactness is as much a property of calculation as it is of
 | >  data sources.  A language having latent types does not obviate
 | >  the programmer's expectation that a calculation involving
 | >  transcendental functions should return an inexact result.
 | 
 | But if error-free results happen to be available, we should
 | therefore disregard them?  What?!

FreeSnell calculates optical properties from measured refractive-index
tables.  That lone exact 0 in the denominator becomes +/0. and is
discarded -- if the Scheme implementation doesn't signal an error!

 | >      An operation may, however, return an exact result if it can
 | >      prove that the value of the result is unaffected by the
 | >      inexactness of its arguments.  For example, multiplication
 | >      of any number by an exact zero may produce an exact zero
 | >      result, even if the other argument is inexact.
 | >
 | >  By those sentences, inexactness is a contagious property of all
 | >  numbers; except 0, the only number whose exactness is
 | >  contagious!  This conflicts with the statement earlier in 6.2.2:
 | 
 | No... by those sentences, inexactness in the sense of possible
 | error propagates forward from arguments into results wherever we
 | cannot prove that the inexactness doesn't introduce the possibility
 | of error in results.  A multiplication by an exact zero is only one
 | of many possibilities here.

What other exact argument to multiplication gives an exact result
despite other arguments being inexact?

 | > | and in doing so it creates a type distinction where none was
 | > | before.
 | >
 | > Is exactness this "type distinction"?
 | 
 | Yep.  What you're doing is declaring that in some circumstances we
 | have to pretend we are uncertain of our results even though there
 | is a mathematical certainty that they are correct.  The sole
 | purpose for this is to fulfill an expectation that inexact results
 | will be returned; you are valuing numeric type above reporting
 | correct answers.

Having one "error-free" number among millions of approximations is of
no practical use; and it interferes with the calculation in more than
one R5RS-compliant implementation.

 | > | In the dialect spec'd by R5RS, there was never any situation
 | > | where an inexact number was required and an exact one would
 | > | not do; thus it was entirely correct for implementations to
 | > | return exact numbers whenever the opportunity presented
 | > | itself.
 | >
 | >Implementations like Elk, Gambit, and Mzscheme signal errors for
 | >division by exact zero, but return infinities for division by
 | >inexact zero.  This is a "situation where an inexact number was
 | >required and an exact one would not do".
 | 
 | That wasn't behavior specified by R5RS, was it?

No, it was behavior allowed by R5RS.

 | That was the decision of a few implementors, who created an
 | inconsistency and a type distinction.  This inconsistency was not
 | created by the standard, and does not need to be "fixed" in the
 | standard.

If it doesn't say you can't; then you can.  Which text in R5RS
prohibits this inconsistency or type distinction?

 | > This created the contradiction noted above.  With exact 0 being
 | > stronger than inexact 0.0, it also leads to the opaque practice
 | > of controlling the behavior of EXPT and `/' at 0 by coercing the
 | > exactness of its arguments.
 | 
 | "strength" has nothing to do with it.  It is merely a mathematical
 | fact.  Any number may be multiplied by zero to get zero.  If there
 | is no uncertainty that the zero is the correct value (ie, if it's
 | an "exact" zero in R5RS parlance) it does not matter a bit whether
 | there is certainty about the other operand.  Differences in the
 | value of the other operand do not introduce any mathematical
 | uncertainty (inexactness) that the result of zero is correct.
 | Infinity in the sense of "some number too large to represent" is no
 | exception to this rule; Infinity in the sense of a true
 | mathematical infinity is, but the result of such a multiplication
 | is neither exact nor inexact; it is a NaN.

Already the case in SRFI-70:

  (* 0 +/0.)                             ==>  0/0.

You may not like the word "strength", but you are describing the same
thing: a 0 which is stronger than 0.0 under multiplication.

 | > I do a lot of numerical computing (near-field optics lately).
 | > Division by zero happens.  If SIN of some complicated expression
 | > returns an exact zero .001% of the time, then .001% of the time I will
 | > get an exception from the division taking that expression as a divisor
 | > rather than an infinity which lets the program continue.
 | 
 | This problem belongs to your implementation, not to R5RS.
 | It would be perfectly compliant with R5RS and consistent
 | treatment of numbers if your system raised an exception
 | in both cases or returned an error object (such as an
 | infinity or a NaN) in both cases.

It sounds like you are you asserting that one can't write a portable
numerical application in Scheme relying on just R5RS.  SRFI-70 intends
to make numeric portability easier.

 | >That is broken behavior; but that is what R5RS-compliant Mzscheme 205
 | >does; and probably other implementations also.
 | 
 | I don't argue with you that it is broken behavior; but I
 | don't see the point in predicating changes to the standard
 | based on a few implementations' inconsistent treatment of
 | exact and inexact numbers.

The purpose of standards is to reduce inconsistency between
implementations.

			      -=-=-=-=-

[Richardson1968]

  D. Richardson,
  Some Undecidable Problems Involving Elementary Functions of a Real
  Variable,
  Journal of Symbolic Logic, Volume 33, Number 4, Dec. 1968, pp514--520.