TAOCP 4.3.1 Exercise 2
Let the $m$ given nonnegative $n$-place integers be (u^{(1)}_{n-1}\ldots u^{(1)}_0)_b,\; (u^{(2)}_{n-1}\ldots u^{(2)}_0)_b,\; \ldots,\; (u^{(m)}_{n-1}\ldots u^{(m)}_0)_b,
Section 4.3.1: The Classical Algorithms
Exercise 2. [15] Generalize Algorithm A so that it does "column addition," obtaining the sum of $m$ nonnegative $n$-place integers. (Assume that $m \le b$.)
Verified: yes
Solve time: 1m25s
Solution
Let the $m$ given nonnegative $n$-place integers be
$$ (u^{(1)}_{n-1}\ldots u^{(1)}_0)b,; (u^{(2)}{n-1}\ldots u^{(2)}_0)b,; \ldots,; (u^{(m)}{n-1}\ldots u^{(m)}_0)_b, $$
where $m\le b$. Their sum is to be formed as
$$ (w_r w_{r-1}\ldots w_0)_b, $$
where $r=n+\lceil\log_b m\rceil$ is sufficient to accommodate the largest possible sum.
The method of Algorithm A extends directly by adding one column at a time and propagating a carry. Since $m\le b$,
$$ u^{(1)}_j+\cdots+u^{(m)}_j+k \le m(b-1)+(m-1) = mb-1 < b^2, $$
because $m\le b$. Hence the carry produced at each stage is a one-place integer.
Algorithm C (Column addition of $m$ nonnegative integers).
C1. [Initialize.] Set $j\leftarrow0$, $k\leftarrow0$.
C2. [Add column.] Set
$$ t\leftarrow u^{(1)}_j+u^{(2)}_j+\cdots+u^{(m)}_j+k. $$
Then set
$$ w_j\leftarrow t\bmod b, \qquad k\leftarrow \lfloor t/b\rfloor . $$
C3. [Loop on $j$.] Increase $j$ by one. If $j<n$, return to step C2.
C4. [Output remaining carry.] While $k>0$, set
$$ w_j\leftarrow k\bmod b, \qquad k\leftarrow \lfloor k/b\rfloor , \qquad j\leftarrow j+1. $$
Terminate.
To prove correctness, let
$$ S_j=\sum_{r=1}^{m}u^{(r)}_j . $$
After processing columns $0,1,\ldots,j-1$, the invariant is
$$ \sum_{i=0}^{j-1} w_i b^i + k b^j = \sum_{i=0}^{j-1} S_i b^i . $$
For $j=0$ this is
$$ 0+0=0. $$
Assume the invariant holds before step C2. Write
$$ t=S_j+k. $$
Since
$$ w_j=t\bmod b, \qquad k'=\lfloor t/b\rfloor, $$
we have
$$ t=w_j+b k'. $$
Multiplying by $b^j$ gives
$$ S_j b^j+k b^j = w_j b^j+k' b^{j+1}. $$
Adding this equation to the induction hypothesis yields
$$ \sum_{i=0}^{j} w_i b^i + k' b^{j+1} = \sum_{i=0}^{j} S_i b^i, $$
which is the invariant for the next value of $j$.
After the loop terminates at $j=n$,
$$ \sum_{i=0}^{n-1} w_i b^i + k b^n = \sum_{r=1}^{m} (u^{(r)}_{n-1}\ldots u^{(r)}_0)_b . $$
Step C4 merely expands the remaining carry $k$ into radix-$b$ digits, preserving equality. Consequently the resulting digits $w_i$ represent exactly the sum of the $m$ given integers.
Therefore Algorithm C correctly performs column addition of $m$ nonnegative $n$-place integers when $m\le b$.
$$ \boxed{\text{Algorithm C above computes the sum of }m\text{ nonnegative }n\text{-place integers by column addition.}} $$