Conversion between Stream Representations

  The signed binary representation is generally more appropriate than the dyadic representation for implementing most operations. This is because firstly there are a small finite number of digits, which means we can examine different combinations of digits at the start of input streams and treat them as individual cases, and also each signed binary digit occupies a fixed amount of space and cannot swell in size like the dyadic digit representation. Certain algorithms, however, are easier to define using the dyadic digit representation, either as an intermediate representation, or for both input and output.

The fact that we use two representations means that it is sometimes necessary to convert between them. We show here how this is performed for the stream representations. The (mantissa, exponent) representations are converted by performing the appropriate conversion on the mantissa and leaving the exponent unchanged.

Converting signed binary streams to dyadic streams is trivial, and is performed by generating a stream with dyadic ones, zeros, and minus ones in place of the corresponding signed binary digits.

Converting dyadic streams into signed binary representations is more complex. It is necessary to examine two digits of the dyadic input stream to decide one digit of output. The conversion function $\mathrm{d\_to\_s}$ is defined as follows:

$$\begin{array} {l} \mathrm{d\_to\_s}(a::b::x) = \left \{ \beg... ....\ \quad \textrm{where } a' = a \oplus \frac{b}{2}\end{array}$$

The conversion function works because the value attached to the remainder of the stream x using the `cons' operation in the recursive call to $\mathrm{d\_to\_s}$ is always in the range [-1,1], and as such can be represented by a single dyadic digit.

We prove of correctness as follows. The value a' represents the value of the first two digits of input. The number represented by the whole input stream is $a' \pm \frac{1}{4}$ because the remainder of the stream (x), which represents a value in the range $[-\frac{1}{4},\frac{1}{4}]$. Now, if a' is greater or equal to a quarter, the entire input stream is in the range [0,1] and can be represented by the signed binary stream whose first digit is one. Similarly if a' is a value between minus a quarter and a quarter the whole stream is in the range $(-\frac{1}{2}, \frac{1}{2})$ and can be represented by an output stream whose first digit is zero, and if a' is a less than or equal to minus a quarter the whole stream is in the range [-1, 0] and can be represented by an output stream whose first digit is minus one. We output the appropriate digit in each case, and convert the remainder of the dyadic input stream by attaching the remainder of the output digit subtracted from a' to x and calling the conversion function recursively.