Output positive digits

Positive digits are output if the numerator x is of the form (1::0::x') or (1::1::x'). If so, we can immediately say

$$x \in \Big[\frac{1}{4},1\Big] \qquad \frac{x}{4y} \in \Big[\frac{1}{16},1\Big]$$

The obvious strategy here would be to generate the digit one (1) in the output stream. Unfortunately if we do so it apparently becomes very complicated to express the remainder of the result as a recursive call (doing so would probably require examination of more digits of the input streams x and y). An algorithm which outputs signed binary digits must exist as the representations used are all equivalent, but would probably be significantly more complex than the one presented here and require a larger lookahead.

The solution is to output a dyadic digit instead of a signed binary one, and to determine which digit by considering the result r of subtracting the denominator y from the numerator x. Let

r = y-x

Now, we examine the first two digits of r. There are three different possible cases to consider:

Case 1:

The result r starts (1::1) or (1::0). Hence

$$r \in \Big[\frac{1}{4},1\Big]$$

We can deduce further that as x can be no greater than 1, and y is no less than $\frac{1}{4}$, r can be no greater than $\frac{3}{4}$. Similarly,

$$x \in \Big[\frac{1}{2},1\Big] \qquad y \in \Big[\frac{1}{4},\frac{3}{4}\Big]$$

$$\Rightarrow \frac{x}{4y} \in \Big[\frac{1}{6},1\Big] \qquad \textrm{and }\qquad r \in \Big[\frac{1}{4},\frac{3}{4}\Big]$$

Observe now that

$$r \in \Big[\frac{1}{4},\frac{3}{4}\Big] \qquad \Rightarrow \qquad (r-y) \in \Big[-\frac{1}{2},\frac{1}{2}\Big]$$

So we can represent the value r' = 2(r-y) = 2(x-2y) in a stream. Now:

Case 2:

The result r starts $(\overline{1}::1)$, , or $(1::\overline{1})$. Therefore:

$$r \in \Big[-\frac{1}{2},\frac{1}{2}\Big]$$

And we can represent r' = 2r = 2(x-y) in a stream. Now:

Case 3:

The result r starts $(\overline{1}::\overline{1})$ or $(\overline{1}::0)$. Hence

$$r \in \Big[-1,-\frac{1}{4}\Big]$$

We can deduce further that as x can be no less than $\frac{1}{4}$, and y is no greater than 1, and therefore r can be no less than $-\frac{3}{4}$. Furthermore we can deduce:

$$x \in \Big[\frac{1}{4},\frac{3}{4}\Big] \qquad y \in \Big[\frac{1}{2},1\Big]$$

$$\Rightarrow \frac{x}{4y} \in \Big[\frac{1}{16},\frac{3}{8}\B... ... \textrm{and }\qquad r \in \Big[-\frac{3}{4},-\frac{1}{4}\Big]$$

We cannot use r to express the result in terms of a digit and a recursive call directly, so we define r' as

$$r' = x - \frac{y}{2} = r + \frac{y}{2} \qquad \in \Big[-\frac{1}{2},\frac{1}{2}\Big]$$

As 2r' is in [-1,1], we can represent r'' = 2r' = 2x - y in a stream. Now, we can find a recursive call as follows: