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