TAOCP 4.4 Exercise 6

Exercise 6. [30] Discuss using Methods 1a, 1b, 2a, and 2b when $b$ or $B$ is $-2$.

Verified: yes
Solve time: 5m29s

Setup

Methods 1a, 1b, 2a, and 2b are defined for conversion between positional systems of radix $b$ and radix $B$. The exercise asks for a discussion of these methods when one of the radices is $-2$.

A radix-$(-2)$ representation of an integer has the form

$$ u=\sum_{k=0}^{m}u_k(-2)^k, \qquad u_k\in{0,1}. $$

Every integer possesses a unique such representation. Fractional representations are obtained by allowing negative powers of $-2$.

The problem is to determine how the four conversion methods behave when either the source radix or the target radix equals $-2$.

Solution

Methods 1a and 2a require repeated division or multiplication by the target radix $B$. Therefore the essential question is whether division and multiplication by a negative radix still produce valid digits.

For radix $B=-2$, every integer $u$ can be written uniquely in the form

$$ u=(-2)q+r, \qquad r\in{0,1}. $$

Indeed, if $u$ is even, take $r=0$ and $q=-u/2$; if $u$ is odd, take $r=1$ and $q=(1-u)/2$. Thus repeated division by $-2$ yields digits $r\in{0,1}$ exactly as repeated division by a positive radix yields ordinary radix digits.

Hence Method 1a remains valid without modification. Starting from $u$, compute

$$ u=(-2)q_0+r_0, $$

then

$$ q_0=(-2)q_1+r_1, $$

and continue until a quotient $0$ is reached. The digits are

$$ (r_m\cdots r_1r_0)_{-2}. $$

Conversely, if the source radix is $-2$ and the target radix is a positive radix $B$, Method 1b remains valid. The representation

$$ u=(u_m\cdots u_0)_{-2} $$

is evaluated by Horner's rule:

$$ \bigl(\cdots((u_m(-2)+u_{m-1})(-2)+u_{m-2})\cdots\bigr)(-2)+u_0. $$

The only difference from the positive-radix case is that the repeated multiplication is by $-2$ instead of $2$.

Method 2a converts fractions by repeated multiplication by the target radix. When $B=-2$, define

$$ u_{k+1}=-2u_k-r_k, $$

where $u_0=u$ and $r_k\in{0,1}$ is chosen so that

$$ -1<u_{k+1}\le0. $$

Since $u_k\in(-1,0]$, the quantity $-2u_k$ lies in $[0,2)$, and exactly one choice of $r_k\in{0,1}$ places $u_{k+1}$ back into $(-1,0]$. Then

$$ u = r_0(-2)^{-1} +r_1(-2)^{-2} +r_2(-2)^{-3} +\cdots . $$

Thus a fractional analogue of Method 2a exists. The interval that must be preserved is no longer $[0,1)$; it is convenient to use $(-1,0]$.

Method 2b also survives unchanged in principle. If

$$ u=(0.u_{-1}u_{-2}\ldots u_{-m})_{-2}, $$

then

$$ u = u_{-1}(-2)^{-1} +u_{-2}(-2)^{-2} +\cdots +u_{-m}(-2)^{-m}, $$

and Horner's rule gives

$$ \bigl((\cdots(u_{-m}/(-2)+u_{1-m})/(-2)+\cdots+u_{-2})/(-2)+u_{-1}\bigr)/(-2). $$

The divisions are now by $-2$ rather than by a positive radix.

A significant distinction appears for fractions. Since

$$ (-2)^{-1}=-\frac12, \qquad (-2)^{-2}=\frac14, \qquad (-2)^{-3}=-\frac18, \ldots, $$

the signs alternate. Consequently a radix-$(-2)$ fraction does not correspond to digits extracted from successive positive fractional parts. The quantities generated during Methods 2a and 2b alternate in sign, and the customary interval $[0,1)$ must be replaced by a suitable interval such as $(-1,0]$.

Another distinction is that the set of numbers having terminating radix-$(-2)$ expansions is exactly the set of dyadic rationals,

$$ \frac{k}{2^n}, \qquad k,n\in\mathbb Z,\ n\ge0, $$

because every finite radix-$(-2)$ expansion equals

$$ \sum_{j=-n}^{m} a_j(-2)^j = \frac{N}{2^n} $$

for some integer $N$. Thus termination properties are the same as for radix $2$.

Verification

For integers, the division step

$$ u=(-2)q+r,\qquad r\in{0,1}, $$

is always possible and unique. If

$$ (-2)q+r=(-2)q'+r', \qquad r,r'\in{0,1}, $$

then

$$ 2(q-q')=r-r'. $$

The right-hand side belongs to ${-1,0,1}$, hence must be $0$. Therefore $r=r'$ and $q=q'$.

For fractions, suppose

$$ u=\sum_{j=1}^{\infty} r_{j-1}(-2)^{-j}. $$

Multiplying by $-2$ gives

$$ -2u = r_0+\sum_{j=1}^{\infty} r_j(-2)^{-j}, $$

so extraction of the digit $r_0$ and repetition of the process reproduces the remaining digits. This is the exact analogue of Method 2a.

Therefore all four methods remain applicable when one radix is $-2$, provided that remainders are chosen from ${0,1}$ and that the treatment of fractions accounts for the alternating signs of the powers of $-2$.

Notes

The arithmetic difficulties introduced by radix $-2$ are conceptual rather than structural. Methods 1a and 1b work almost verbatim. Methods 2a and 2b require a different normalization interval because powers of $-2$ alternate in sign, but the same multiplication and division principles continue to apply. The terminating representations are precisely the dyadic rationals, exactly as in ordinary binary notation.

$$ \boxed{\text{All four methods remain valid for radix }-2,\text{ with digits }0,1\text{ and appropriate handling of alternating signs.}} $$