TAOCP 4.1 Exercise 14

Section 4.1: Positional Number Systems

Exercise 14. [**] [14] Multiply $(1132)_{i-1}$ by itself in the quater-imaginary system using the method illustrated in the text.

Verified: no
Solve time: 4m02s

Exercise 4.1.14 [**]

Problem: Multiply $(1132)_{i-1}$ by itself in the quater-imaginary system using the method illustrated in the text.

Solution:

Let $b = 2i$. Then the quater-imaginary number $(1132)_{i-1}$ has the value

$$ (1132)_{i-1} = 1\cdot b^3 + 1\cdot b^2 + 3\cdot b + 2. $$

Compute the powers of $b$:

$$ b^0 = 1, \quad b^1 = 2i, \quad b^2 = (2i)^2 = -4, \quad b^3 = (2i)^3 = -8i, \quad b^4 = (2i)^4 = 16. $$

Substitute:

$$ (1132)_{i-1} = 1\cdot(-8i) + 1\cdot(-4) + 3\cdot(2i) + 2 = -8i - 4 + 6i + 2 = -2 - 2i. $$

Step 1: Set up multiplication in quater-imaginary system

We perform multiplication digit by digit, as in the text. Let

$$ (1132){i-1} = (a_3 a_2 a_1 a_0){i-1}, \quad a_3 = 1, a_2 = 1, a_1 = 3, a_0 = 2. $$

The product $(1132){i-1} \cdot (1132){i-1}$ is obtained by the standard "long multiplication" algorithm adapted to base $2i$, where each partial product is shifted according to powers of $b$ and then the resulting digits are reduced modulo 4 with appropriate carrying to ensure digits are in ${0,1,2,3}$.

Step 2: Multiply as polynomials in $b$

Write

$$ (1132)_{i-1} = a_3 b^3 + a_2 b^2 + a_1 b + a_0. $$

Then

$$ (1132){i-1}^2 = (a_3 b^3 + a_2 b^2 + a_1 b + a_0)^2 = \sum{i=0}^{6} c_i b^i, $$

where each $c_i$ is obtained by summing products of coefficients corresponding to $b^i$. Compute each $c_i$:

$b^6$ term: $a_3^2 = 1^2 = 1 \implies c_6 = 1$.
$b^5$ term: $2 a_3 a_2 = 2\cdot 1 \cdot 1 = 2 \implies c_5 = 2$.
$b^4$ term: $2 a_3 a_1 + a_2^2 = 2\cdot 1\cdot 3 + 1^2 = 6 + 1 = 7 \implies c_4 = 7$.
$b^3$ term: $2 a_3 a_0 + 2 a_2 a_1 = 2\cdot1\cdot2 + 2\cdot1\cdot3 = 4 + 6 = 10 \implies c_3 = 10$.
$b^2$ term: $2 a_2 a_0 + a_1^2 = 2\cdot1\cdot2 + 3^2 = 4 + 9 = 13 \implies c_2 = 13$.
$b^1$ term: $2 a_1 a_0 = 2 \cdot 3 \cdot 2 = 12 \implies c_1 = 12$.
$b^0$ term: $a_0^2 = 2^2 = 4 \implies c_0 = 4$.

Thus before carrying, we have the "raw" polynomial:

$$ c_6 b^6 + c_5 b^5 + c_4 b^4 + c_3 b^3 + c_2 b^2 + c_1 b + c_0 = b^6 + 2 b^5 + 7 b^4 + 10 b^3 + 13 b^2 + 12 b + 4. $$

Step 3: Reduce digits modulo 4 with carrying

In the quater-imaginary system:

All digits must be in ${0,1,2,3}$.
For $b = 2i$, a "carry" of 4 in position $b^k$ produces $1$ in $b^{k+2}$ and reduces the $b^k$ digit by 4.

Apply the carrying rules from low to high powers.

Step 3a: $b^0$ term

$c_0 = 4$.
4 in $b^0$ carries $1$ to $b^2$:

$$ b^0: 4 - 4 = 0, \quad b^2: 13 + 1 = 14. $$

Step 3b: $b^1$ term

$c_1 = 12$.
12 divided by 4 gives 3 carries of 1 to $b^3$:

$$ b^1: 12 - 12 = 0, \quad b^3: 10 + 3 = 13. $$

Step 3c: $b^2$ term

$c_2 = 14$ (after previous carry)
14 divided by 4 gives 3 carries of 1 to $b^4$:

$$ b^2: 14 - 12 = 2, \quad b^4: 7 + 3 = 10. $$

Step 3d: $b^3$ term

$c_3 = 13$
13 divided by 4 gives 3 carries of 1 to $b^5$:

$$ b^3: 13 - 12 = 1, \quad b^5: 2 + 3 = 5 $$

Step 3e: $b^4$ term

$c_4 = 10$ (after previous carry)
10 divided by 4 gives 2 carries of 1 to $b^6$:

$$ b^4: 10 - 8 = 2, \quad b^6: 1 + 2 = 3 $$

Step 3f: $b^5$ term

$c_5 = 5$ (after previous carry)
5 divided by 4 gives 1 carry of 1 to $b^7$:

$$ b^5: 5 - 4 = 1, \quad b^7: 0 + 1 = 1 $$

Step 3g: $b^6$ term

$c_6 = 3$ (after previous carry)
Already less than 4, no change.

All higher terms ($b^7$) are $c_7 = 1$.

Step 4: Final quater-imaginary numeral

Collect all digits from $b^7$ down to $b^0$:

$$ (1132){i-1}^2 = (1 ; 3 ; 2 ; 1 ; 2 ; 0 ; 0){i-1}. $$

Check:

$b^7 = b^7$ digit 1
$b^6 = 3$
$b^5 = 1$
$b^4 = 2$
$b^3 = 1$
$b^2 = 2$
$b^1 = 0$
$b^0 = 0$

So the canonical quater-imaginary representation is:

$$ \boxed{(1321200)_{i-1}}. $$

Step 5: Verification (optional)

Compute the value using powers of $b = 2i$:

\begin{aligned} b^0 \cdot 0 & = 0 \ b^1 \cdot 0 & = 0 \ b^2 \cdot 2 & = 2 \cdot (-4) = -8 \ b^3 \cdot 1 & = 1 \cdot (-8i) = -8i \ b^4 \cdot 2 & = 2 \cdot 16 = 32 \ b^5 \cdot 1 & = 1 \cdot 32i = 32i \ b^6 \cdot 3 &