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

Quote:

>>        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.

--
============================================================================

============================================================================

Sat, 16 Jan 1993 21:06:23 GMT
An alternative to floating point (was Re: Floating point non-exactness)

The reals calculator mentioned is available from titan.rice.edu via
anonymous ftp, in the file public/C_calc.tar.Z and an help file in
public/calc.instr.  Have fun...

--
"The Movement You Need is on Your Shoulder"
- John Lennon's favorite line from "Hey, Jude"

Sat, 16 Jan 1993 23:54:58 GMT
An alternative to floating point (was Re: Floating point non-exactness)
Also see HAKMEM (MIT AI Memo #239, Feburary 1972) Item #101, where
representation.  There are simple algorithms for adding, subtracting,
multiplying, and dividing infinite streams of continued fraction
coefficients to produce more streams and, of course, all rational
numbers come out even.
--
-Colin

Sun, 17 Jan 1993 08:01:34 GMT
An alternative to floating point (was Re: Floating point non-exactness)

Quote:

>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.

I also had this idea, (of representing real numbers as functions that
'generate' them).  The apeal is of course that finally you have something
that is TRUELY a real number (in the mathamatical sence), not just an
approximation.  Or do you?  After all the real number are supposed to
be uncountable, but our representations are program text, and hence
countable.  Thus it seems our representation can't be the real number as
we know an love them.

So where is the problem?  Actually we have no problem defining most of the
operators (+,-,*,/,<...limit) and proving that they all have the properties
necessary to be the real number, so it seems that we have a valid
candidate for representing the real numbers exactly.  The problem is
more subtle.

The root the the problem seems to be the = (equality) operator.  In
our representation it is NOT a total function.   (that is it must answer
'i don't know' (Bottom) for some inputs.  After all, suppose I
give you two functions that compute PI in two ratically different ways
how do you show that these two functions are =?  You can't just look
at digits (or approximations), since no matter how long you look, you
don't know if you looked far enough.  In some cases a proof will decide
the matter, but this will NOT work in general (Godels theorem).

Now this it not to say the method does not have merit, if fact, if anything
I believe it casts doubt on  wheter the real number system 'EXISTS' in
any pratical sence.  (After all, the only 'real' numbers we EVER deal
with are the ones that we manipulate in some way.  These happen to be
EXACTLY those which can be repesented by programs).

I can't explore these issues as much as I would like at present, but
hopefully in the future I will have the opertunity.  I would like to
see what properties this new algebra has and how it relates to the
standard real numbers.  I would certainly love to hear from anyone
who may have insights in this matter.

This study I believe could have practical benefits.  After all we don't
use the '=' operator much in real number computations (for exactly the
reason that it is unreliable).  Thus it seems from a practical point
of view we have already given up =.  On the other hand, it would be nice
to be able to specify a precision at the END of the computation and have
the precisions back propagate so that intermediate results are computed
to a precision necessary to insure the precision of the final result.
The representation of real numbers as functions naturally has this
property, and I suspect that it could be made efficient enough to
satisfy people who to numerical analysis for a living.

Vance

Sun, 17 Jan 1993 23:29:45 GMT
An alternative to floating point (was Re: Floating point non-exactness)
Here's a brief bibliography of implementing exact reals.  These
implementations are by necessity of the _constructive reals_, that is,
those reals for which one can give an algorithm to produce arbitrarily
accurate approximations.

Hans-J. Boehm, "Constructive real interpretation of numerical
programs," SIGPLAN Notices, 22(7):214-221. July 1987

Hans-J. Boehm, Robert Cartwright, Mark Riggle, and Michael J.
O'Donnell, "Exact real arithmetic:  A case study in higher order
programming."  In Proceedings of the 1986 Lisp and Functional
Programming Conference, pp 162-173, 1986.

Vernon Lee and Hans-J. Boehm, "Optimizing programs over the
constructive reals."  In Proceedings of the ACM SIGPLAN '90 Conference
on Programming Language Design and Implementation, pp 102-111, June
1990.

Jean Vuillemin, "Exact real computer arithmetic with continued
fractions."  Research Report 760, INRIA, 1987.

Jean Vuillemin, "Exact real computer arithmetic with continued
fractions."  In ACM Conference on Lisp and Functional Programming, pp.
14-27.  ACM, July 1988.

Jerry Schwartz, "Implementing Infinite Precision Arithmetic."  9th
Symposium on Computer Arithmetic, 1989.

These works address implementing a system that requires only that the
programmer provide a requested accuracy for real values - the packages
automatically produce the required accuracy.  Many other works have
studied an approach that puts the programmer more in charge of producing
the accuracy, by for example raising the precision of a multiple-precision
arithmetic package.

--
"The Movement You Need is on Your Shoulder"
- John Lennon's favorite line from "Hey, Jude"

Mon, 18 Jan 1993 02:29:01 GMT
An alternative to floating point (was Re: Floating point non-exactness)

I also had this idea, (of representing real numbers as functions that
'generate' them).  The apeal is of course that finally you have something
that is TRUELY a real number (in the mathamatical sence), not just an
approximation.

...[discussion on the difficulty of "=" for reals as functions] ...

Now this it not to say the method does not have merit, if fact, if anything
I believe it casts doubt on  wheter the real number system 'EXISTS' in
any pratical sence.  (After all, the only 'real' numbers we EVER deal
with are the ones that we manipulate in some way.  These happen to be
EXACTLY those which can be repesented by programs).

I can't explore these issues as much as I would like at present, but
hopefully in the future I will have the opertunity.  I would like to
see what properties this new algebra has and how it relates to the
standard real numbers.  I would certainly love to hear from anyone
who may have insights in this matter.

Vance

You may want to look into work done on constructive reals.  A very good
reference (though requiring some mathematical background) is "Constructive
Analysis" by Bishop and Bridges (Springer-Verlag: 1980, ISBN 0-387-15066-8).

Since testing the equality of two reals is not decidable (in general), there
are weaker (decidable) notions that can be used instead.

As computer technology improves, I can forwee having special "constructive
real" processors, just has we now have math co-processors (which actually only
do finite precision floating point arithmetic).

-- Young-il

Mon, 18 Jan 1993 03:54:13 GMT
An alternative to floating point (was Re: Floating point non-exactness)
Here's a reference to another article on constructive reals:

Vernan A. Lee Jr. and Hans-J. Boehm
"Optimizing programs over the constructive reals"
ACM SIGPLAN'90 Conf. on Pgm'g Lang. Design and Impl.
White Plains, NY, June 20-22, 1990
(SIGPLAN Notices v. 25, n. 6, June 1990)
pp 102-111

Mon, 18 Jan 1993 19:51:15 GMT

 Page 1 of 1 [ 11 post ]

Relevant Pages