1<HTML> 2<HEAD> 3<TITLE>Constructive Real Calculator and Library Implementation Notes</title> 4</head> 5<BODY BGCOLOR="#FFFFFF"> 6<H1>Constructive Real Calculator and Library Implementation Notes</h1> 7</body> 8The calculator is based on the constructive real library consisting 9mainly of <TT>com.sgi.math.CR</tt> and <TT>com.sgi.math.UnaryCRFunction</tt>. 10The former provides basic arithmetic operations on constructive reals. 11The latter provides some basic operations on unary functions over the 12constructive reals. 13<H2>General approach</h2> 14The library was not designed to use the absolute best known algorithms 15and to provide the best possible performance. To do so would have 16significantly complicated the code, and lengthened start-up times for 17the calculator and similar applications. Instead the goals were to: 18<OL> 19<LI> Rely on the standard library to the greatest possible extent. 20The implementation relies heavily on <TT>java.math.BigInteger</tt>, 21in spite of the fact that it may not provide asymptotically optimal 22performance for all operations. 23<LI> Use algorithms with asymptotically reasonable performance. 24<LI> Keep the code, and especially the library code, simple. 25This was done both to make it more easily understandable, and to 26keep down class loading time. 27<LI> Avoid heuristics. The code accepts that there is no practical way 28to avoid diverging computations. The user interface is designed to 29deal with that. There is no attempt to try to prove that a computation 30will diverge ahead of time, not even in cases in which such a proof is 31trivial. 32</ol> 33A constructive real number <I>x</i> is represented abstractly as a function 34<I>f<SUB>x</sub></i>, such that <I>f<SUB>x</sub>(n)</i> produces a scaled 35integer approximation to <I>x</i>, with an error of strictly less than 362<SUP><I>n</i></sup>. More precisely: 37<P> 38|<I>f<SUB>x</sub></i>(<I>n</i>) * 2<SUP><I>n</i></sup> - x| < 2<SUP><I>n</i></sup> 39<P> 40Since Java does not support higher order functions, these functions 41are actually represented as objects with an <TT>approximate</tt> 42function. In order to obtain reasonable performance, each object 43caches the best previous approximation computed so far. 44<P> 45This is very similar to earlier work by Boehm, Lee, Cartwright, Riggle, and 46O'Donnell. 47The implementation borrows many ideas from the 48<A HREF="http://reality.sgi.com/boehm/calc">calculator</a> 49developed earlier by Boehm and Lee. The major differences are the 50user interface, the portability of the implementation, the emphasis 51on simplicity, and the reliance on a general implementation of inverse 52functions. 53<P> 54Several alternate and functionally equivalent representations of 55constructive real numbers are possible. 56Gosper and Vuillemin proposed representations based on continued 57fractions. 58A representation as functions 59producing variable precision intervals is probably more efficient 60for larger scale computation. 61We chose this representation because it can be implemented compactly 62layered on large integer arithmetic. 63<H2>Transcendental functions</h2> 64The exponential and natural logarithm functions are implemented as Taylor 65series expansions. There is also a specialized function that computes 66the Taylor series expansion of atan(1/n), where n is a small integer. 67This allows moderately efficient computation of pi using 68<P> 69pi/4 = 4*atan(1/5) - atan(1/239) 70<P> 71All of the remaining trigonometric functions are implemented in terms 72of the cosine function, which again uses a Taylor series expansion. 73<P> 74The inverse trigonometric functions are implemented using a general 75inverse function operation in <TT>UnaryCRFunction</tt>. This is 76more expensive than a direct implementation, since each time an approximation 77to the result is computed, several evaluations of the underlying 78trigonometric function are needed. Nonetheless, it appears to be 79surprisingly practical, at least for something as undemanding as a desk 80calculator. 81<H2>Prior work</h2> 82There has been much prior research on the constructive/recursive/computable 83real numbers and constructive analysis. Relatively little of this 84has been concerned with issues related to practical implementations. 85<P> 86Several implementation efforts examined representations based on 87either infinite, lazily-evaluated decimal expansions (Schwartz), 88or continued fractions (Gosper, Vuillemin). So far, these appear 89less practical than what is implemented here. 90<P> 91Probably the most practical approach to constructive real arithmetic 92is one based on interval arithmetic. A variant that is close to, 93but not quite, constructive real arithmetic is described in 94<P> 95Oliver Aberth, <I>Precise Numerical Analysis</i>, Wm. C. Brown Publishers, 96Dubuque, Iowa, 1988. 97<P> 98The issues related to using this in a higher performance implementation 99of constructive real arithmetic are explored in 100<P> 101Lee and Boehm, "Optimizing Programs over the Constructive Reals", 102<I>ACM SIGPLAN 90 Conference on Programming Language Design and 103Implementation, SIGPLAN Notices 25</i>, 6, pp. 102-111. 104<P> 105The particular implementation strategy used n this calculator was previously 106described in 107<P> 108Boehm, Cartwright, Riggle, and O'Donnell, "Exact Real Arithmetic: 109A Case Study in Higher Order Programming", <I>Proceedings of the 1101986 ACM Lisp and Functional Programming Conference</i>, pp. 162-173, 1986. 111</body> 112</html> 113