TAOCP 4.3.1 Exercise 31

Section 4.3.1: The Classical Algorithms

Exercise 31. [**] [28] Assume that $b = 3$ and that $u = (u_{m+n-1} \ldots u_1 u_0)3$, $v = (v{n-1} \ldots v_1 v_0)3$ are integers in balanced ternary notation (see Section 4.1), $v{n-1} \ne 0$. Design a long-division algorithm that divides $u$ by $v$, obtaining a remainder whose absolute value does not exceed $\frac{1}{2}|v|$. Try to find an algorithm that would be efficient if incorporated into the arithmetic circuitry of a balanced ternary computer.

Verified: yes
Solve time: 5m23s

Exercise 4.3.1.31 [28], Balanced Ternary Long Division with Remainder Bound

Let

$$ u=(u_{m+n-1}\cdots u_1 u_0)3, \qquad v=(v{n-1}\cdots v_1 v_0)_3, $$

where the digits are balanced ternary,

$$ u_i, v_i \in {-1,0,1}, \qquad v_{n-1}\ne 0. $$

We wish to divide $u$ by $v$ to obtain a quotient $q$ with balanced ternary digits and a remainder $r$ satisfying

$$ |r|\le \frac12 |v|. $$

The goal is an algorithm suitable for balanced ternary hardware, in which each quotient digit requires only addition, subtraction, or no operation.

Step 1: Normalize the divisor

Multiply $u$ and $v$ by $-1$ if necessary to ensure

$$ v_{n-1} = 1. $$

Define

$$ V = (v_{n-1}\cdots v_0)_3. $$

Step 2: Choose the initial power index

Let $m$ be the smallest integer such that

$$ \frac12 3^m |V| \le |u| < \frac32 3^m |V|. $$

Such an $m$ exists because scaling $V$ by powers of 3 covers all positive magnitudes in overlapping intervals of length $3/2$.

Set the initial partial remainder

$$ R_{m+1} = u. $$

Step 3: Inductive step for quotient digits

We determine quotient digits $q_j\in {-1,0,1}$ for $j = m, m-1, \dots, 0$.

Suppose $q_m, q_{m-1}, \dots, q_{j+1}$ have been determined. Define the partial remainder

$$ R_{j+1} = u - \sum_{k=j+1}^{m} q_k 3^k V. $$

We maintain the invariant

$$ |R_{j+1}| < \frac32 3^j |V|. $$

Step 4: Determine the next quotient digit

Write

$$ R_{j+1} = 3^j V x_j, \qquad x_j = \frac{R_{j+1}}{3^j V}. $$

By the invariant,

$$ |x_j| < \frac32. $$

Choose $q_j$ to be the nearest integer in ${-1,0,1}$ to $x_j$:

$$ q_j = \begin{cases} 1,& x_j > \frac12,\ 0,& -\frac12 \le x_j \le \frac12,\ -1,& x_j < -\frac12. \end{cases} $$

Set the next partial remainder

$$ R_j = R_{j+1} - q_j 3^j V = 3^j V (x_j - q_j). $$

Since $q_j$ is the nearest integer to $x_j$,

$$ |x_j - q_j| \le \frac12, $$

$$ |R_j| \le \frac12 3^j |V| < \frac32 3^{j-1} |V|. $$

Thus the invariant holds for the next step.

Step 5: Completion

Proceed inductively for $j = m, m-1, \dots, 0$. At the final stage,

$$ R_0 = u - \sum_{k=0}^m q_k 3^k V. $$

Define

$$ q = (q_m \cdots q_0)_3, \qquad r = R_0. $$

Then

$$ u = qV + r, \qquad |r| \le \frac12 |V|. $$

Since $V$ is a normalized form of $v$ ($v_{n-1} = 1$), we also have

$$ |r| \le \frac12 |v|. $$

Step 6: Hardware considerations

Each quotient digit $q_j$ is determined by comparing $R_{j+1}$ with $\pm \frac12 3^j V$. In balanced ternary hardware, this comparison can be performed digitwise, using only the leading digits and propagation of carries. Then one performs

$$ R_j = \begin{cases} R_{j+1} - 3^j V,& q_j = 1,\ R_{j+1},& q_j = 0,\ R_{j+1} + 3^j V,& q_j = -1. \end{cases} $$

No multiplication is required, only shifts by powers of 3 and addition or subtraction. Balanced ternary allows negative values directly, so no separate borrow mechanism is necessary.

Step 7: Summary of the algorithm

Normalize so that $v_{n-1} = 1$.
Choose $m$ such that $\frac12 3^m |V| \le |u| < \frac32 3^m |V|$.
Set $R_{m+1} = u$.
For $j = m, m-1, \dots, 0$:

$$ q_j = \text{nearest integer in } {-1,0,1} \text{ to } \frac{R_{j+1}}{3^j V},\quad R_j = R_{j+1} - q_j 3^j V. $$ 5. Output $q = (q_m \cdots q_0)_3$, $r = R_0$.

This algorithm produces a balanced ternary quotient and a remainder satisfying

$$ |r| \le \frac12 |v|. $$

It is efficient in hardware, requiring only ternary shifts, addition, and subtraction.