next up previous contents
Next: Dyadic Digit Operations Up: Conclusion Previous: Evaluation of Implementation

Possible Extensions and Future Work

In chapter 1 we described many approaches to exact real arithmetic. Unfortunately it is very difficult to compare these approaches. One direction for future work would be to perform a theoretical comparison of these approaches. One could also implement systems using the different approaches and compare their performance in some standardised way.

The performance achieved in the calculator implemented is poor when compared with commercial implementations of high precision floating point arithmetic. It would be interesting to implement an optimised version of these operations in an imperative language.

It may be possible to achieve improved performance by parallelising some of the algorithms. For example, many of the algorithms developed exhibit some form of branching. One simple approach to parallelising these would be to allocate evaluation of the stream on each branch of the expression to different processors.

Chapter 7 gives some theoretical analysis of the basic algorithms. An interesting idea would be to analyse these algorithms in more detail, possibly extending it to the transcendental functions too, and investigate their complexity. In particular it would be interesting to see what minimum bounds on the lookahead and complexity exist, and whether they are achieved here or are achievable using other algorithms on these representations.

Another observation about the calculator is that although some numerals must be represented using an infinite number of digits, we sometimes know that a number is represented exactly by a finite portion of the numeral. Suppose, for example, we wish to compute a simple expression (eg. (2+3)), because we know that in fact the numbers can be represented exactly by a finite number of digits, we need never perform more than a finite amount of the computation. The current approach will output correct result, but would then continue computing indefinitely. If we were to introduce a terminator and allow computations with finite length numerals as well as infinite length ones, we may be able to improve performance on rational computations and allow the system to stop when the result is computed exactly.

The use of signed binary digits may not be the most effective digit representation for arithmetic operations. It may turn out that similar algorithms applied to a digit in a larger (eg. 215) or smaller base (eg. the golden ratio [8,9]) may be more efficient, either in a theoretical sense, or by exploiting the fact that all operations on integers which may be represented in one word are executed in the same time, regardless of their size. It would be interesting to investigate this possibility further.

Lastly, in section 7.1.6 we saw how the form of an expression could affect its computational complexity. One interesting area for development which might also be useful in other approaches to exact real arithmetic would be to develop a compiler for optimising exact real arithmetic which used some strategy (heuristic or otherwise) to manipulate or re-arrange expressions to make them simpler to compute. This might even involve techniques from computer algebra which could perform more complex simplifications than merely re-arranging of expressions.

next up previous contents
Next: Dyadic Digit Operations Up: Conclusion Previous: Evaluation of Implementation
Martin Escardo