|fx(n) * 2n - x| < 2n
Since Java does not support higher order functions, these functions
are actually represented as objects with an approximate
function. In order to obtain reasonable performance, each object
caches the best previous approximation computed so far.
This is very similar to earlier work by Boehm, Lee, Cartwright, Riggle, and
The implementation borrows many ideas from the
developed earlier by Boehm and Lee. The major differences are the
user interface, the portability of the implementation, the emphasis
on simplicity, and the reliance on a general implementation of inverse
Several alternate and functionally equivalent representations of
constructive real numbers are possible.
Gosper and Vuillemin proposed representations based on continued
A representation as functions
producing variable precision intervals is probably more efficient
for larger scale computation.
We chose this representation because it can be implemented compactly
layered on large integer arithmetic.
pi/4 = 4*atan(1/5) - atan(1/239)
All of the remaining trigonometric functions are implemented in terms
of the cosine function, which again uses a Taylor series expansion.
The inverse trigonometric functions are implemented using a general
inverse function operation in UnaryCRFunction. This is
more expensive than a direct implementation, since each time an approximation
to the result is computed, several evaluations of the underlying
trigonometric function are needed. Nonetheless, it appears to be
surprisingly practical, at least for something as undemanding as a desk
Several implementation efforts examined representations based on
either infinite, lazily-evaluated decimal expansions (Schwartz),
or continued fractions (Gosper, Vuillemin). So far, these appear
less practical than what is implemented here.
Probably the most practical approach to constructive real arithmetic
is one based on interval arithmetic. A variant that is close to,
but not quite, constructive real arithmetic is described in
Oliver Aberth, Precise Numerical Analysis, Wm. C. Brown Publishers,
Dubuque, Iowa, 1988.
The issues related to using this in a higher performance implementation
of constructive real arithmetic are explored in
Lee and Boehm, "Optimizing Programs over the Constructive Reals",
ACM SIGPLAN 90 Conference on Programming Language Design and
Implementation, SIGPLAN Notices 25, 6, pp. 102-111.
The particular implementation strategy used n this calculator was previously
Boehm, Cartwright, Riggle, and O'Donnell, "Exact Real Arithmetic:
A Case Study in Higher Order Programming", Proceedings of the
1986 ACM Lisp and Functional Programming Conference, pp. 162-173, 1986.