TAOCP 4.1 Exercise 3

**Exercise 4.

taocpmathematicsalgorithmsvolume-2hard

Section 4.1: Positional Number Systems

Exercise 3. [29] Express $-49 + i$ in the quarter-imaginary system.

Verified: yes
Solve time: 13m

Exercise 4.1.3, Problem 3 [29]

Express $-49+i$ in the quarter-imaginary system, that is, in base $2i$.

Solution

Let

$$ -49+i=\sum_{k} d_k(2i)^k, \qquad d_k\in{0,1,2,3}. $$

A standard property of the quarter-imaginary system is that the even and odd powers separate:

$$ (2i)^{2k}=(-4)^k, \qquad (2i)^{2k+1}=2i(-4)^k. $$

Hence

$$ \sum_k d_k(2i)^k = \sum_k d_{2k}(-4)^k + 2i\sum_k d_{2k+1}(-4)^k. $$

Therefore:

  • the digits in the even positions represent the real part in base $-4$;
  • the digits in the odd positions represent $y/2$ in base $-4$, where $y$ is the imaginary coefficient.

1. Represent $-49$ in base $-4$

Repeated division by $-4$ gives

$$ -49=(-4)(13)+3, $$

$$ 13=(-4)(-3)+1, $$

$$ -3=(-4)(1)+1, $$

$$ 1=(-4)(0)+1. $$

Reading the remainders upward,

$$ -49 = 1113_{(-4)}. $$

Thus the even-position digits are

$$ d_6d_4d_2d_0=1113. $$

2. Represent $y/2=1/2$ in base $-4$

Since

$$ 1.2_{(-4)} = 1+2(-4)^{-1} = 1-\frac12 = \frac12, $$

we have

$$ \frac12 = 1.2_{(-4)}. $$

Thus the odd-position digits are obtained from the base-$(-4)$ digits of $1.2$:

$$ d_1=1, \qquad d_{-1}=2, $$

and all higher odd-position digits are $0$.

3. Interleave the digits

Combining the even and odd positions:

$$ \begin{array}{c|cccccccc} \text{position} & 6 & 5 & 4 & 3 & 2 & 1 & 0 & -1\ \hline d_k & 1 & 0 & 1 & 0 & 1 & 1 & 3 & 2 \end{array} $$

Hence

$$ -49+i = 1010113.2_{,2i}. $$

Verification

$$ \begin{aligned} 1010113.2_{2i} &=(2i)^6+(2i)^4+(2i)^2+(2i)^1+3+2(2i)^{-1}\ &=(-64)+16+(-4)+2i+3+2!\left(-\frac{i}{2}\right)\ &=-49+i. \end{aligned} $$

Therefore the quarter-imaginary representation is

$$ \boxed{1010113.2_{,2i}}. $$

$\square$