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

*To*: srfi-70@xxxxxxxxxxxxxxxxx*Subject*: Re: inexactness vs. exactness*From*: William D Clinger <will@xxxxxxxxxxx>*Date*: Wed, 27 Jul 2005 08:48:36 +0200*Delivered-to*: srfi-70@xxxxxxxxxxxxxxxxx*User-agent*: Gnus/5.110003 (No Gnus v0.3) XEmacs/21.5-b20 (berkeley-unix)

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. > So, does R5RS permit an inexact number which only one mathematical > number rounds to? Yes, certainly. Below I will describe two implementations of R5RS inexact arithmetic that have this property: the computable reals, and the inexact rationals with exact i/o. (Under the unfortunate influence of a flawed paper that was presented at the 2004 Scheme Workshop, several Scheme programmers have been incanting that it is not Scheme's inexact numbers that are inexact, but certain arithmetic operations that are inexact. There is a grain of truth in that slogan, but it seems to have led some people to an incorrect conclusion: that they can identify the inexact operations. With R5RS arithmetic, *which* operations are inexact is determined by the implementation, not by the R5RS or by the programmers. The computable reals are an important example of this fact.) * * * The computable reals. The R5RS permits an implementation to represent an inexact complex number x as a specially tagged procedure that, given any positive exact rational epsilon, returns an approximation to x that is within epsilon of the true value. With this representation, all of the standard arithmetic operations are exact on inexact as well as on exact complex numbers. Indeed, this is one of the standard ways in which operations on the real numbers are defined in mathematics. Division by zero is an error, of course---and this cannot be strengthened to signal an error, on pain of non-computability. Even so, the / procedure can be made to run in constant time, even when its second argument is zero. The STRING->NUMBER procedure is trivial with this representation, and is perfectly exact. The problems arise with the comparison predicates (which are defined only on reals) and with the NUMBER->STRING procedure. Part of the problem is that we have to know whether the imaginary part of an inexact number is zero before we can tell whether the number is real, and testing for zero is undecidable in general. One solution to that is to interpret "real" as having an *exact* zero as the imaginary part, which Bradley Lucier recommended to us way back in 1998. To implement the comparison predicates, one might extend the domain of the specially tagged procedures that represent inexact reals to include a special flag, say an exact 0, that causes the procedure to return +1 if the number it represents is positive, -1 if the number it represents is negative, and to return 0 or never return if the number it represents is zero. It is then the programmer's responsibility to avoid testing the sign of zero, just as it is to avoid division by zero. Another approach, which is probably more practical, is to make the comparison predicates inexact: instead of always returning the correct boolean value when they return, but sometimes failing to return, they could compute an approximation and compare the approximations. This won't always return the correct answer, but that flakiness is explicitly allowed by the following R5RS note: "While it is not an error to compare inexact numbers using these predicates, the results may be unreliable because a small inaccuracy may affect the result; this is especially true of = and zero?. When in doubt, consult a numerical analyst." This sort of thing has been implemented, e.g. by Hans Boehm, and is considerably more efficient than you might think. * * * Inexact rationals with exact i/o. The R5RS permits an implementation in which all inexact reals are represented by specially tagged exact rationals. Then the string->number and number->string procedures can be exact. The rational arithmetic operations (+, -, *, /) could also be exact on rational numbers, so only the irrational operations (sqrt etc) would be inexact. Another possibility is to make the rational arithmetic operations inexact by limiting the precision of the result to the precision of the most precise argument. This makes the conversion operations exact, but the arithmetic operations inexact. * * * I think the implementations described above are good ones to keep in mind when discussing the semantics of R5RS arithmetic. Will

**Follow-Ups**:**Re: inexactness vs. exactness***From:*Michael Sperber

**Re: inexactness vs. exactness***From:*Aubrey Jaffer

- Prev by Date:
**Re: inexactness vs. exactness** - Next by Date:
**Re: inexactness vs. exactness** - Previous by thread:
**Re: inexactness vs. exactness** - Next by thread:
**Re: inexactness vs. exactness** - Index(es):