Next: Terminology and Notation Up: A Calculator for Exact Previous: Linear Fractional Transformations

# Representations

In chapter 2 we discussed real arithmetic in general and the inadequacy of the usual binary or decimal representations for real number computation. In this chapter we define the representations that will be used in this work and some of their general properties. We also briefly discuss the issues that arise when we develop algorithms for these representations, show how to convert between the two basic stream representations, how to convert a decimal numeral into the signed binary representation, and how to convert a finite portion of a signed binary stream back into decimal.

Two basic representations are used for reals in the closed interval [-1,1]; streams of signed binary digits and streams of dyadic rationals treated as digits. These representations are then used to derive a representation for the whole real line, and another which simplifies the implementation of transcendental functions later on.

The signed binary stream representation is used as the main representation for the calculator. However the use of dyadic rationals as digits greatly simplifies certain algorithms, in particular division and the functional operations, and is used as an intermediate representation in these cases. In chapter 7, we show how algorithms for the same operation using these two superficially similar representations can perform very differently, and the observations from the analyses performed here form one of the justifications for not using the dyadic stream representation more extensively.

Next: Terminology and Notation Up: A Calculator for Exact Previous: Linear Fractional Transformations
Martin Escardo
5/11/2000