Determining output digits

Suppose we have inputs (x,y,z) where

$$\llbracket x \rrbracket \leq \llbracket y \rrbracket \leq \llbracket z \rrbracket$$

We examine the first digits of x and z, and use simple analysis of the range of possible reals represented, as described in section 3.6.2 to determine whether or not we can determine digits of a stream representing $\llbracket y \rrbracket$ using only the known digits of x and z.

Having examined a some finite number of digits from x and z, we will encounter on of three qualitatively distinct cases; either we can say that $\llbracket x \rrbracket \neq \llbracket z \rrbracket$, or we can find a digit or digits whose range encloses all possible values of $\llbracket y \rrbracket$, or we cannot find such a digit but cannot say that $\llbracket x \rrbracket \neq \llbracket z \rrbracket$. In the first case it is safe to cease examination of x and z and use y to return the remainder of the result. In the second and third cases we must continue to examine x and z, generating digits where possible, until we can say for certain that $\llbracket x \rrbracket \neq \llbracket z \rrbracket$.

Suppose the ranges r = [r_min, r_max] and s = [s_min,s_max] contain the lower and upper bounds x and z of y. There are a number of possible situations that may arise. Figure 5.1 illustrates with some examples.

  

Figure 5.1: Limit cases

Case 1:

The lower and upper bounds are too far apart to determine a digit, and ranges are disjoint. Therefore lower and upper bounds not equal and we can safely return y.

Example 1 illustrates such a situation.

Case 2:

We can find a digit such whose range encloses [r_min, s_max]. Output this digit and examine the inputs further.

In example 2, we can deduce that the range of y is [0,1], so we can generate the digit 1 as the first digit of y. Similarly in example 3, the range of y must be $\big[-\frac{1}{2}, 0 \big ]$, so we can generate the digits $(0::\overline{1})$ (or equivalently $(\overline{1}::1)$).

Example 4 is an interesting possibility which would be handled by here. We can see that the least possible value of the lower bound r_min is equal to the greatest possible value of the upper bound s_max. We can deduce that this is the only possible value for y and output it directly without examining further inputs or intervals.

Case 3:

We cannot find a digit such whose range encloses [r_min, s_max], but we cannot say for certain that the lower and upper end-points are not equal. Therefore we must examine more digits of the end-points.

Example 5 falls into this category. Suppose the numeral $x = (\overline{1}::\overrightarrow{1})$ and $z = (1::\overrightarrow{-1})$, we can see that $\llbracket x \rrbracket = \llbracket z \rrbracket = 0$. If this were the case, we would have to output the number zero (eg. the numeral $\overrightarrow{0}$) without examining y or any further intervals by the condition stated in section 5.1. We must therefore examine further digits of x and z until either we can ascertain that they are both equal, or we can generate a digit as in examples 2, 3, or 4.