aet@felix.ee.mu.OZ.AU (Albert Edward THOMPSON) (03/28/91)
I am trying to implement real numbers in a normal-order functional language-- NOT floating point numbers or any other approximation. This is my problem: I don't know what real numbers are or even whether they can exist in any pragmatic (i.e. computational) sense. I looked at Bishop's 'Constructive Analysis' but could work out how to construct only rational reals. I've heard about some things called the computable reals. (some sort of countable subset of the reals?) What are they? Are there reals which are not computable? If so, in what way do they "exist"? Concretely, my picture of real arithmetic on computer is something like this: user> sqrt 2 machine> answer1 ;machine gives answer in unforced form. user> answer1 5 ;user asks to see answer in explicit form accurate to 5 decimal places. machine> 1.41421 ;machine forces answer as asked for. user> log pi machine> answer2 user> answer2 8 machine> 1.14472988 It is not important whether the machine rounds off (which it probably must do anyway) or gives the "true" digits in the decimal expansion. (although this is theoretically interesting -- comments welcome!) What is important is that the machine should do much work only when digits are explicitly requested and that the machine ideally should give _any_ accuracy. Perhaps some symbolic maths language uses reals rather than approximations? Sorry if I'm being nebulous or ill-informed: I still don't know exactly what is required in this problem. Preemptive thanks for any suggestions, Bert.
edgar@function.mps.ohio-state.edu (Gerald Edgar) (03/28/91)
In article <7197@munnari.oz.au> aet@felix.ee.mu.OZ.AU (Albert Edward THOMPSON) writes: > > I am trying to implement real numbers in a normal-order functional language-- There is a "calculator" for Suns that does this. It cites these references: Hans-J. Boehm, "Constructive Real Interpretation of Numerical Programs", Proceedings of the SIGPLAN '87 Symposium on Interpreters and Interpretive Techniques, SIGPLAN Notices 22, 7 (July 1987), pp. 241-221. Hans-J. Boehm, R. Cartwright, Michael J. O'Donnell, and Mark Riggle, "Exact Real Arithmetic: A Case Study in Higher Order Programming", Proceedings of the 1986 Lisp and Functional Programming Conference, pp. 162-173. Brent, R.P., "Fast Multiple-Precision Evaluation of Elementary Functions", Journal of the ACM 23, (1976), pp. 242-251. -- Gerald A. Edgar Department of Mathematics Bitnet: EDGAR@OHSTPY The Ohio State University Internet: edgar@mps.ohio-state.edu Columbus, OH 43210 ...!{att,pyramid}!osu-cis!shape.mps.ohio-state.edu!edgar
straub@jogger.cs.umd.edu (Pablo A. Straub) (03/29/91)
In article <7197@munnari.oz.au> aet@felix.ee.mu.OZ.AU (Albert Edward THOMPSON) writes: >I am trying to implement real numbers in a normal-order functional language-- >NOT floating point numbers or any other approximation. >This is my problem: > I don't know what real numbers are > or even whether they can exist in any pragmatic (i.e. computational) sense. You may want to look at Hans Bohem and Robert Cartwright Exact real numbers: Formulating real numbers as functions In Research Topics in Functional Programming Edited by David A. Turner University of Texas at Austin Year of Programming Series Addison Wesley 1990 ---- Pablo A. Straub, straub@cs.umd.edu
boehm@parc.xerox.com (Hans Boehm) (03/29/91)
Another more recent, but less general, reference is "Optimizing Programs over the Constructive Reals", PLDI '90, (appeared as SIGPLAN Notices 25, 6), by Vernon Lee and myself. The calculator now runs on a variety of UNIX workstations. It can be obtained by anonymous ftp from arisia.xerox.com:~ftp/pub/C_calc.tar.Z. This is mostly automatically generated C code. Send mail if you want the real source. Hans-J. Boehm (boehm@xerox.com)
fs@caesar.cs.tulane.edu (Frank Silbermann) (04/03/91)
In article <91090.154205NN1@awiwuw11.wu-wien.ac.at> NN1@awiwuw11.wu-wien.ac.at writes: > there are several equivalent ways to define the notion > of computable real number. > > A number a is computable, if the n-th digit of a is > a recursive function of n, or, equivalently, > if the set of all rational numbers <= a > is recursive (assuming some coding scheme for rational numbers). > ... > Now for the more practical quesiton raised by A.E. Thomson, > how real numbers should indeed be represented on a computer, > so that at any stage one can get as many digits as requested, > ... >Heinrich Rolletschek >k310670@AEARN One difficulty with this definition would be the problem of asking for the first 5 mantissa digits of an expression that simplifies to: _ 0.099999999999999999999999999999999999999999999 (9's forever). Clearly, the result equals 0.1 exactly, so the first five mantissa digits OUGHT to be 0.10000, yet, most naive systems would report 0.09999 !!! If computation with real numbers is to be "computable," we need a more lenient requirement than "ability to compute any single digit in a finite amount of time," and we need a more lenient notion of approximation than "truncation of the digits." The problem is that, in mathematics, equality is defined via convergence of infinite chains of approximations, and _not_ by the ability to produce identical normal forms. [MORAL: This should be a lesson to those who believe functional programming should be based on some arbitrary lambda calculus or rewriting system. It should be based on domain theory, which takes into account the existence of infinite chains of approximation. Also, consider the fact that mathematics has not given us any single notation suitable for expressing _every possible_ computable function over the reals (or even the rationals). This may be a hint that we should not worry too much if our functional programming languages are not "fully abstract," that our domain contains objects which cannot be denoted by any expression in our language. ] -- Frank Silbermann fs@cs.tulane.edu Tulane University New Orleans, Louisiana USA -- Frank Silbermann fs@cs.tulane.edu Tulane University New Orleans, Louisiana USA
boehm@parc.xerox.com (Hans Boehm) (04/03/91)
Aberth makes the observation however that if instead of asking for the first n digits in the infinite expansion, I ask for the best rounded n digit approximation (where I'm counting digits to the right of the decimal point), and I occasionally allow the machine to give me the best n+1 digit rounded approximation instead, then the result is computable, provided I can approximate the number to an arbitrarily small tolerance, i.e. I'm starting with a recursive real number. I simply evaluate the number to a tolerance of less than one in the n+2nd digit. If the n+1st and n+2nd digits are 5 and 0, then I print the first n digits followed by a 5. In all other cases, I can safely round to n digits. (This is of course not optimal.) I can also ask for the first n truncated digits if I use a redundant notation, e.g. if I allow digits -9 through -1 as well. Of course that gets hard to read ... Hans (boehm@xerox.com)
rjc@cstr.ed.ac.uk (Richard Caley) (04/03/91)
In article <6878@rex.cs.tulane.edu>, Frank Silbermann (fs) writes:
fs> Also, consider the fact that mathematics
fs> has not given us any single notation
fs> suitable for expressing _every possible_
fs> computable function over the reals (or even the rationals).
Apologies if I am being slow, but if a function is computable does
that not imply that it can be denoted in some notational scheme which
someone has decided is a reasonable model of `computation' (e.g. TMs,
Markov Algorithms or whatever).
If `computable' is deleted from the sentance quoted it becomes an
obvious tautology, so I must be missing something.
BTW: has anyone mentioned Boehm & Cartwright's paper in `Research
Topics in Functional Programming'? They argue that the reals
should be represnted as functions not as digit sequences for
efficiancy reasons(!). (full reference on demand, I don't have
it with me).
--
rjc@cstr.ed.ac.uk Wandered in from sci.lang to ask dumb questions.suarez@prl.dec.com (Ascander Suarez) (04/04/91)
In article <7197@munnari.oz.au>, aet@felix.ee.mu.OZ.AU (Albert Edward THOMPSON) writes:
I am trying to implement real numbers in a normal-order functional language--
NOT floating point numbers or any other approximation.
This is my problem:
I don't know what real numbers are
or even whether they can exist in any pragmatic (i.e. computational) sense.
...
There is an article at the lisp and Functional Programming conference 1988 entitled:
Exact Real Computer Arithmetic with Continued Fractions
by Jean Vuillemin
The author presents a representation of the computable real numbers and
algorithms for their manipulation.
Ascander Suarez
suarez@decprl.dec.comjgk@osc.COM (Joe Keane) (04/05/91)
We can characterise constructive real numbers by the primitive operations that are provided on them. For example, one way to describe the numbers in [0,2[ is by the following operations: return the integer part of a given real (0 or 1) return twice the fractional part of a given real (another real) make a new real given its integer part and twice its fractional part It should be clear that these operations are all that is needed. Given them, you can write functions to add two numbers, and so on. I have restricted the numbers to [0,2[ for simplicity, but i trust you will see that this isn't a problem. These operations suggest a simple implementation. We can represent a real number by a (possibly lazy) list of 0 or 1. Then the two operations are just car, cdr, and cons on the representation. Here is another set of operations which can define real numbers: return the integer part of a given real return the reciprocal of the fractional part of a given real make a new real given its integer part and the reciprocal of its fractional part These operations suggest a different simple implementation. We can represent a real number by a list of integers which is its continued fraction expansion. Again the operations are just car, cdr, and cons. There's no reason for us to think that either or these sets of operations (or some other) is the `right' one to define real numbers. Rather, given an implementation which directly supports a set of operations powerful enough to define the reals, we can implement the other operations in terms of these. For a given implementation, some operations are primitive (they work directly on the representation) and some are generic, built from primitive operations. Now we can code up any number of implementations, and if they support the basic operations, they will work together. That is, we can add together a number in binary form and one in continued fraction form without any problem. Although these operations seem intuitive, there's a problem with them. They are too strict, because they require exact tests. For example taking the integer part leaves no room for error: floor(0.9999) = 0 while floor(1.0000) = 1. So in place of a strict test like x > 0, we can have an operation like this: given x return either x < 1 or x > -1 Note that the results overlap. By allowing a choice of return values for some range of arguments, we eliminate the problems of strict tests. A similar operation is the following: given x and a positive number epsilon, return either x < 0, x > 0, or |x| < epsilon In this case we can provide a tolerance as small as we want, but not zero. Of course by providing a smaller tolerance we can expect the test to take longer. I hope you see that these operations are equivalent, assuming we also have some simple ones like `double a number'. Tests like this suggest a redundant number representation. It's been recognized since Turing that redundant representations are the way to go. With a non-redundant representation, even such a simple thing as adding two numbers can require you to look at an unbounded number of digits of the arguments. In contrast, a redundant representation allows you to generate the result `on the fly' with a minimal (bounded) amount of look-ahead. Of course people want to see numbers in decimal or test if they're positive, so we have to convert to a non-redundant form some time. But by delaying this as long as possible, we eliminate most of the problems with things looking too far ahead. When there is such a problem, it's because the user asked a question which is hard to answer, and not because we did something wrong. So how do you implement these things? Well, all you have to do is pick the right set of combinators, and algorithms to go with them. Of course this makes it sound simple. Really a lot of problems (compiling programs for example) can be reduced to ``pick the right set of combinators'' (plus algorithms to use them of course). That may give some insight, but it doesn't necessarily make it easy. -- Joe Keane, supercombinator hacker jgk@osc.com (...!uunet!stratus!osc!jgk)
johnsson@cs.chalmers.se (Thomas Johnsson) (04/05/91)
In article <1991Apr4.095619.27416@prl.dec.com> suarez@prl.dec.com (Ascander Suarez) writes: >There is an article at the lisp and Functional Programming conference 1988 entitled: > >Exact Real Computer Arithmetic with Continued Fractions >by Jean Vuillemin > >The author presents a representation of the computable real numbers and >algorithms for their manipulation. This paper also appeared recently in IEEE Transactions on Computers, which I think i a more detailed version. Thomas Johnsson (johnsson@cs.chalmers.se) Dept. of CS, Chalmers University of Technology, S-412 96 Goteborg, Sweden phone: dept: +46 (0)31 721088.
tom@nw.stl.stc.co.uk (04/05/91)
digits in the infinite expansion, I ask for the best rounded n digit
approximation (where I'm counting digits to the right of the decimal point),
and I occasionally allow the machine to give me the best n+1 digit rounded
approximation instead, then the result is computable, provided I can
approximate the number to an arbitrarily small tolerance, i.e. I'm starting
with a recursive real number. I simply evaluate the number to a tolerance of
less than one in the n+2nd digit. If the n+1st and n+2nd digits are 5 and 0,
then I print the first n digits followed by a 5. In all other cases, I can
safely round to n digits. (This is of course not optimal.) I can also
ask for the first n truncated digits if I use a redundant notation, e.g.
if I allow digits -9 through -1 as well. Of course that gets hard to read ...
======
Stuff and nonsense! How do you know when you are close enough? A recursive
real number is simply a function f:N->R satisfying a convergence constraint (and
of course being recursive too) [R=2 * N * (N-{0}), ie the rationals]. I don't
see how you can use the convergence constraint to know when your approximation
is close enough to be right to so many decimal places (suppose f is identically
zero on the first twenty milliion naturals, and 1 thereafter: how do you know
after looking at 10 million terms that you still don't have the first digit?
how do you know after looking at the first 50 million terms that you do now h
the first digit?)fs@rex.cs.tulane.edu (Frank Silbermann) (04/08/91)
>> Also, consider the fact that mathematics >> has not given us any single notation >> suitable for expressing _every possible_ >> computable function over the reals (or even the rationals). In article <RJC.91Apr3095056@brodie.cstr.ed.ac.uk> rjc@cstr.ed.ac.uk (Richard Caley) writes: > Apologies if I am being slow, but if a function is computable, > does that not imply that it can be denoted in some notational > scheme which someone has decided is a reasonable model > of `computation' (e.g. TMs, Markov Algorithms or whatever). A Turing-complete formalism can _model_ the computation of any computable function. That does not mean that every such formalism can _directly express_ every computable function. For instance, you can model any parallel computation with a sequential Turing machine, but you cannot using a sequential Turing machine to _directly express_ parallel computation. Most mathematicians working with real arithmentic care only that their ad-hoc notations communicate the concepts and relations (e.g. functions) that interest them at the moment. Most do not concern themselves that their notation is complete -- i.e. that they have set up a language suitable for expressing every possible computable function over the reals. When the topic of discourse changes, the notation is enriched as needed. When trying to design a functional programming language to work with objects of a given semantic domain, I analogously argue that we ought not require that the function from syntax to semantic domain (expressed by the denotational equations) be "onto", i.e. that full abstraction is a luxury we cannot always afford. (This has nothing to do with the language's Turing equivalence.) Frank Silbermann fs@cs.tulane.edu Tulane University New Orleans, Louisiana USA
aet@mullian.ee.mu.OZ.AU (Albert Edward THOMPSON) (04/09/91)
It seems androids dream of computable reals. >Article 742 of comp.lang.functional: >Subject: Re: do computers believe in real numbers? >Summary: They do, but languages tend not to. >Keywords: redundant representation >Reply-To: jgk@osc.COM (Joe Keane) I'm the bloke who posted the query on real numbers. I found your posting very interesting, but there're a few bits i'm not sure about. >We can characterise constructive real numbers by the primitive operations that >are provided on them. For example, one way to describe the numbers in [0,2[ >is by the following operations: > return the integer part of a given real (0 or 1) > return twice the fractional part of a given real (another real) > make a new real given its integer part and twice its fractional part > >It should be clear that these operations are all that is needed. Given them, >you can write functions to add two numbers, and so on. I have restricted the >numbers to [0,2[ for simplicity, but i trust you will see that this isn't a >problem. integerPart: |R -> {0,1} twiceFractionPart: |R -> |R makeReal: {0,1} x |R -> |R Wouldn't you need another function to create a real without starting out with a real in the first place? i.e. no |R on the left of the -> Otherwise this would not be an abstract data type and would be sort of a circular definition. By the way, how do you define functions like sin, cos, log, etc? The series definitions are infinite. In fact, how do you define higher-order functions like derivative, integral, fourierTransform? (I already know the analysis (supposedly :^), but how do you deal with infinite series, limits, etc. in a concrete way? Is there something else that has to be included in the abstract data type to take care of this?) Hey! Your suggestions about lazy continued fraction representation and redundancy in representation sound like the basis of quite a workable implementation. Thanks for a very useful posting! Bert.