next up previous contents
Next: Summary of Analysis Up: A Calculator for Exact Previous: Summary of Experimental Analysis


  In this work we have developed a calculator for exact real number computation and performed a theoretical analysis of the algorithms and experimented on their implementation.

We began by defining two representations of reals in the range [-1,1] using streams of digits. These were then extended to represent real numbers on the whole real line using a (mantissa, exponent) style representation. We showed how to convert between these representations, how to convert decimal numbers into a signed binary representation, and how to convert a finite portion of the signed binary representation back into decimal.

Algorithms for the basic arithmetic operations were implemented for these representations. A number of different techniques are used to obtain these algorithms, including exploiting the relationship between the list operation `cons' and numerical average, using certain identities, and analysing of the range of possible values of a stream starting with a given digit or sequence of digits.

We developed an algorithm for the direct multiplication of two streams of signed binary digit. This is a more complex operation than the multiplication of dyadic digit streams, but avoids the problem of dyadic digit swell which can be observed if the dyadic digit multiplication is used to compute iterations of the logistic map, for example, and which can cripple performance.

We also developed an algorithm for the division of two signed binary numbers. This is significantly more complicated than the familiar school long division method because in the school long division method we know the whole denominator, whereas when dividing by a number with an infinite representation this is not the case. Other approaches such as Fourier's cross-division method (a description of which can be found in [30] p.159-164) which examine the denominator from right to left are also unsuitable because they allow digits which have already been output to be `corrected' later on, and hence each output digit depends on an infinite number of digits of the numerator and denominator.

We also developed an algorithm to compute the limits of Cauchy sequences. As far as we are aware, no other such algorithm has been developed in the literature. This algorithm significantly extends the range of computations which can be performed, and makes the calculator much more flexible. This is because of the many useful functions can be expressed as the limits of Cauchy sequences.

Finding algorithms for the transcendental functions is relatively straightforward once we have the algorithm for computing limits of Cauchy sequences. We simply find a method of generating a suitable Cauchy sequence using the inputs to the function whose limit is the output of the function, and about which we know either the rate, or in some cases just the manner in which the algorithm converges to its limit. The set of transcendental functions implemented here is not exhaustive, but it would be easy to extend the number of functions available using the technique described.

The functional operations integration and function minimum and maximum have also been implemented. The operations on streams (representing reals in the range [-1,1]) are a modification of a Gofer implementation by Reinhold Heckmann. This work has been extended to the whole real line and integrated into the calculator allowing the operations to be applied to functions which use the complete set of arithmetic operations and transcendental functions. This is the first implementation of these algorithms on the whole real line.

A simple user interface has been created to demonstrate the calculator. The interface addresses the problem of allowing the user to view a (potentially time consuming) calculation as it proceeds but also giving an answer which can be used or checked, by outputting signed digits as they are computed and then converting the result into decimal when some specified precision is reached.

next up previous contents
Next: Summary of Analysis Up: A Calculator for Exact Previous: Summary of Experimental Analysis
Martin Escardo