wald@theory.lcs.mit.edu (David Wald) (07/31/90)
In article <3491@goanna.cs.rmit.oz.au> ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes: >In article <622@.tetrauk.UUCP>, rick@.tetrauk.UUCP (Rick Jones) writes: >> 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. -- ============================================================================ David Wald wald@theory.lcs.mit.edu ============================================================================
scorpion@titan.rice.edu (Vernon Lee) (07/31/90)
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"
-=- Vernon Lee -=- Warning: Myers-Briggs INTP -=- scorpion@rice.edu -=-colin@array.UUCP (Colin Plumb) (08/01/90)
Also see HAKMEM (MIT AI Memo #239, Feburary 1972) Item #101, where Gosper raves about the advantages of continued fractions as a numerical 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
morrison@thucydides.cs.uiuc.edu (Vance Morrison) (08/01/90)
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
scorpion@titan.rice.edu (Vernon Lee) (08/02/90)
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"
-=- Vernon Lee -=- Warning: Myers-Briggs INTP -=- scorpion@rice.edu -=-