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