Dyadic digit representation

  There are two obvious representations for the dyadic digits described in section 3.3.2.

1.

As a string of bits representing a binary fraction. This is similar to the representation of an integer, except that the integer is aligned round the least significant digit but a binary fraction around its most significant digit.

2.

As a pair of arbitrary length integers

The choice of representation is arbitrary in the sense that once the primitive operations are defined the choice should the dyadic stream or other algorithms. It may be preferable, however, to use one representation over another.

The first representation has the advantage that it would theoretically require less space if implemented efficiently. Unlike the second representation, there is also no problem with keeping the first representation in its lowest terms as there is only one possible representation of each dyadic rational using the first representation (excluding trailing zeros), but infinitely many for each using the second. We overcome this in the second representation by ensuring that the denominator is always positive and the numerator always odd or zero.

Although the first representation would in theory be more efficient, the second representation was chosen to implement the algorithms. There are two good reasons for this. Firstly, arbitrary length integers are supplied for free in Haskell, making it extremely easy to implement operations using the second representation. In order to use a string of bits to represent dyadic digits, one would have to implement the arithmetic operations from scratch. This is both difficult in a functional language, and less efficient in real terms because it is no longer possible to take advantage of the optimised internal operations on arbitrary length integers. Secondly, it is easier to design, describe, and understand algorithms written using the second representation than using the first.

In actual fact as early implementations of the calculator were written in Gofer (see section 6.2.3), in which arbitrary length integers were not available, and it was therefore necessary to write primitive dyadic digit operations from scratch using the first representation. The algorithms required are modifications of those used for arbitrary length integer arithmetic which are described in detail in [17]. These were subsequently replaced by versions using the arbitrary length integer package later in the development.