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