next up previous contents
Next: Dyadic Rational Streams Up: Representing Reals as Streams Previous: Representing Reals as Streams

Signed Binary Digit Streams

  The first representation makes use of a stream of signed binary digits $\{\overline{1}, 0, 1\}$. This representation is also known as the redundant binary representation on $\mathbb{R}$ [17]. The real number represented by the stream x = (d1::d2::d3::...) is defined as:

\begin{displaymath}
\llbracket x \rrbracket = \sum_{i=1}^{\infty}d_i\!\cdot\!2^{...
 ...} + \frac{d_2}{2^2} + \frac{d_3}{2^3} + \frac{d_4}{2^4} + \dots\end{displaymath}

Hence $\llbracket x \rrbracket \in [-1,1]$. There is a unique representation for the numbers minus one ($\overrightarrow{-1}$) and one ($\overrightarrow{1}$), and infinitely many representations for all other numbers in this range.

We also define the range (see section 3.1) of a finite portion of the stream as follows: Let x' be a list containing the first m digits of x, $\llbracket x' \rrbracket$ is the range of x':

Figure 3.1 shows the range of values represented by the signed binary streams starting with each of the three possible digits.


  
Figure 3.1: The range of streams starting with different digits
\begin{figure}
\begin{center}

\includegraphics [width=7cm]{sbstream.eps}\end{center}\end{figure}

There are two further interesting observations to make. The first is that the following identities exist. We use them frequently when developing algorithms using signed binary streams:

 

The second observation is that the signed binary representation has a fixed rate of convergence. In other words, every new digit in the stream refines the range of possible values taken by the stream at a fixed rate.


next up previous contents
Next: Dyadic Rational Streams Up: Representing Reals as Streams Previous: Representing Reals as Streams
Martin Escardo
5/11/2000