An alternative to floating point (was Re: Floating point non-exactness)

[David Wald]

In article <3491 at goanna.cs.rmit.oz.au> ok at goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes:
>In article <622 at .tetrauk.UUCP>, rick at .tetrauk.UUCP (Rick Jones) writes:
>> 	fpcmp (double a, double b)
>> 
>> 		returns 0 if a equals b within the reliable precision,
>> 		else returns 1 if a > b, or -1 if a < b
>> 
>> Real problem:  how do you write fpcmp() ?
>
>See Knuth, "The Art of Computer Programming", vol 2, "Semi-Numerical Methods"
>...

For an interesting alternative to floating point (albeit, one that
will probably never appear in any recognizable dialect of C, hence the
followup to comp.lang.misc), see

Hans Boehm and Robert Cartwright, "Exact real arithmetic: Formulating
real numbers as functions," in ed. David A. Turner, _Research Topics
in Functional Programming_, Addison-Wesley, 1990, pp43-64

The paper gives an overview of two techniques for performing exact
arithmetic on (constructive) real numbers, in which a real number is
represented either as a digit-generating function or as a function
which, when handed a tolerance (in the form of a rational number)
returns a rational approximation to a given real number.  It's an
interesting idea.

The most amusing idea, for me, was the mention of a (I assume
simulated) desk calculator they've devised with this approach, which
has a "right-shift" button to allow you to shift the window as far to
the right as you like, for as many digits of precision as you need.  I
can just see high school science teachers dealing with students
equipped with calculators like that:

"But that's the right answer! I typed in "1.00" and divided it by
"3.000", and it gave me those 500 digits.  Why is that wrong?"

-David


Other references (from the bibliography of this paper) are:

Boehm, H.-J., Cartwright, R. S., O'Donnell, M. J., and Riggle, M.
"Exact real arithmetic: A case study in higher order programming". In
_Proceedings of the 1986 ACM Conference on Lisp and Functional
Programming_ (Cambridge, Mass., August). ACM, 1986, pp. 162-173

Boehm, H.-J. "Constructive real interpretations of numeric programs".
In _Proceedings of the ACM SIGPLAN '87 Symposium on Interpreters and
Interpretive Techniques. ACM, 1987.


--
============================================================================
David Wald                                           wald at theory.lcs.mit.edu
============================================================================