next up previous contents
Next: Auxiliary operations Up: A Calculator for Exact Previous: Signed decimal fractions to

Basic Operations

  In chapter 3 we defined two basic representations for reals in a closed interval using streams of signed binary digits and streams of dyadic digits. We then used these to define (mantissa, exponent) representations for numbers on the whole real line and a representation of reals as a stream of nested intervals. We also discussed some properties of these representations, and considerations which apply when we define algorithms on them.

In this chapter we give algorithms for the basic arithmetic operations and some useful auxiliary functions used to implement them. The algorithms given here are used to implement the basic arithmetic operations in the calculator, and form the basis for higher level transcendental functions and the functional operations in chapter 5.

The main representation used to implement operations within the calculator is the signed binary (mantissa, exponent) representation. The (mantissa, exponent) representation is required because the stream representations are not closed under addition, subtraction, or division. The signed binary representation is chosen because it is simpler to use when developing certain algorithms, and because it does not suffer from the problem of dyadic digit swell discussed in chapter 7.

In order to implement the (mantissa, exponent) operations addition, subtraction, and multiplication, we use the stream operations average and multiplication (as the stream representations are closed under average and multiplication). These stream operations are also used to implement other algorithms including division.

Although the signed binary stream operation is the main representation used here, the dyadic digit stream representation is also extremely useful as an intermediate representation to simplify the division algorithm, and it is used in Alex Simpson's algorithms for functional operations [26]. In addition, the average and multiplication algorithms for the dyadic stream representation are considerably simpler than those for the signed binary representation, and it is helpful to understand these before developing equivalent algorithms for the signed binary representation.

The chapter is structured as follows. We first develop algorithms for the auxiliary operations, some of which are used with both dyadic and signed binary stream representations, and some of which are only developed for the signed binary streams. Next we give the algorithms for average and multiplication using the dyadic stream representation, and then for the signed binary stream representation. We also give and algorithm for division of a signed binary stream by an integer. Lastly we give the (mantissa, exponent) algorithms for the basic operations addition, subtraction, multiplication, and division.

The algorithms for the primitive operations on dyadic digits using the representation adopted in the implementation, which are required for the algorithms for auxiliary functions and basic operations on dyadic streams, are given in appendix A.

Presented here are algorithms for division of two numbers in the signed binary (mantissa, exponent) representation, and for the direct multiplication of two streams in signed binary representation without going via the dyadic stream representation. These two algorithms are entirely my own work. The remaining algorithms are already known, and the majority of these were described, at least in some a general form, in personal communications with Alex Simpson and Martín Escardó.



 
next up previous contents
Next: Auxiliary operations Up: A Calculator for Exact Previous: Signed decimal fractions to
Martin Escardo
5/11/2000