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