Path: utzoo!attcan!uunet!decwrl!sdd.hp.com!zaphod.mps.ohio-state.edu!uwm.edu!ux1.cso.uiuc.edu!thucydides.cs.uiuc.edu!morrison
From: morrison@thucydides.cs.uiuc.edu (Vance Morrison)
Newsgroups: comp.lang.misc
Subject: Re: An alternative to floating point (was Re: Floating point non-exactness)
Message-ID: <1990Aug1.152945.12826@ux1.cso.uiuc.edu>
Date: 1 Aug 90 15:29:45 GMT
References: <622@.tetrauk.UUCP> <3491@goanna.cs.rmit.oz.au> <1990Jul31.130623.15963@mintaka.lcs.mit.edu>
Sender: usenet@ux1.cso.uiuc.edu (News)
Reply-To: morrison@thucydides.cs.uiuc.edu.UUCP (Vance Morrison)
Organization: University of Illinois, Urbana-Champaign
Lines: 58

In article <1990Jul31.130623.15963@mintaka.lcs.mit.edu> wald@theory.lcs.mit.edu (David Wald) writes:

>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