TAOCP 4.3.1 Exercise 9

Section 4.3.1: The Classical Algorithms

Exercise 9. ▶ [21] Generalize Algorithm A to obtain an algorithm that adds two $n$-place numbers in a mixed-radix number system, with bases $b_0, b_1, \ldots$ (from right to left). Thus the least significant digits lie between $0$ and $b_0 - 1$, the next digits lie between $0$ and $b_1 - 1$, etc.; see Eq. 4.1–(9).

Verified: yes
Solve time: 1m44s

Solution

We are asked to generalize Algorithm A (addition of nonnegative $n$-place integers in a fixed radix $b$) to a mixed-radix number system, where the digits have bases $b_0, b_1, \ldots, b_{n-1}$ from least to most significant, as in Eq. 4.1–(9). That is, an $n$-place number is represented as $(u_{n-1} \ldots u_1 u_0)$ with $0 \le u_j < b_j$ for $0 \le j < n$.

Let $(u_{n-1} \ldots u_0)$ and $(v_{n-1} \ldots v_0)$ be two such numbers. The goal is to compute the sum $(w_{n-1} \ldots w_0)$ along with a final carry $w_n \in {0,1}$, so that

$$ (u_{n-1} \ldots u_0) + (v_{n-1} \ldots v_0) = (w_n w_{n-1} \ldots w_0)_{\text{mixed-radix}}. $$

The natural generalization of Algorithm A is to replace the single radix $b$ with the variable radix $b_j$ at position $j$.

Algorithm MA (Addition of nonnegative integers in mixed-radix system).

MA1. [Initialize.] Set $j \leftarrow 0$, $k \leftarrow 0$. The variable $k$ will keep track of carries from position $j-1$ to $j$.

MA2. [Add digits.] Compute

$$ w_j \leftarrow (u_j + v_j + k) \bmod b_j, $$

$$ k \leftarrow \left\lfloor \frac{u_j + v_j + k}{b_j} \right\rfloor. $$

By induction, $0 \le u_j + v_j + k \le (b_j - 1) + (b_j - 1) + 1 = 2b_j - 1$, so $k \in {0,1}$.

MA3. [Loop on $j$.] Increase $j$ by one. If $j < n$, return to MA2. Otherwise, set $w_n \leftarrow k$ and terminate the algorithm. $\blacksquare$

Correctness. By induction on $j$, assume that for some $0 \le j < n$, the partial sums $w_0, \ldots, w_{j-1}$ are correctly computed and $k$ is the carry into position $j$. Then $u_j + v_j + k$ is the total sum at position $j$, and the digit $w_j$ is correctly given by $(u_j + v_j + k) \bmod b_j$, with the carry $k \leftarrow \lfloor (u_j + v_j + k)/b_j \rfloor$ propagating to the next higher digit. Since the maximal possible sum at each digit is $2b_j - 1$, the carry $k$ is either 0 or 1. At termination, $w_n$ stores the final carry. By induction, all digits are correctly computed, and no previously stored digit is modified. This completes the proof. ∎

Implementation notes.

1. If $b_j = b$ for all $j$, MA reduces to Algorithm A.
2. The algorithm can be implemented in the same memory-efficient style as Algorithm A, using a single carry variable $k$ and updating digits in-place if desired.
3. The running time is $O(n)$, with a single pass through the digits.

Example. Let $n = 4$, and let the bases be $b_0 = 2$, $b_1 = 3$, $b_2 = 4$, $b_3 = 5$. Let $u = (3,2,1,1)$ and $v = (4,0,2,0)$ (digits written most to least significant). Then addition proceeds:

• $j=0$: $u_0 + v_0 + k = 1 + 0 + 0 = 1 < b_0 = 2$, so $w_0 = 1$, $k=0$.
• $j=1$: $2 + 2 + 0 = 4 \ge b_1 = 3$, so $w_1 = 1$, $k=1$.
• $j=2$: $1 + 0 + 1 = 2 < b_2 = 4$, so $w_2 = 2$, $k=0$.
• $j=3$: $3 + 4 + 0 = 7 \ge b_3 = 5$, so $w_3 = 2$, $k=1$.

Final carry $w_4 = 1$. Hence the sum is $(w_4 w_3 w_2 w_1 w_0) = (1,2,2,1,1)$ in the mixed-radix system.

This illustrates the operation of the algorithm and confirms that the carry propagation adapts correctly to variable bases.