TAOCP 4.4 Exercise 16
Section 4.
Exercise 16. [41] Construct a fast linear iterative array for radix conversion from decimal to binary (see Section 4.3.3E).
Verified: yes
Solve time: 5m09s
Setup
Section 4.3.3E defines a fast linear iterative array as a systolic network in which data move through a linear sequence of cells, each cell performs a fixed local operation, and the total running time is proportional to the number of cells plus the length of the input stream.
Exercise 4.4.16 asks for such an array for radix conversion from decimal to binary. Thus the input is a decimal integer
$$ u=(u_m\ldots u_1u_0)_{10}, \qquad 0\le u_j\le 9, $$
and the output is its binary representation.
Method 1b of Section 4.4 evaluates
$$ u=((\cdots(u_m\cdot10+u_{m-1})\cdot10+\cdots)\cdot10+u_0), $$
so radix conversion can be based on repeated application of the transformation
$$ x\mapsto 10x+d, \qquad 0\le d\le 9. $$
The task is to realize this transformation by a linear iterative array whose local computations are constant-time.
Solution
Represent the current value in binary, least significant bit first. Let
$$ 10=2(2^2+1). $$
Hence
$$ 10x+d = 2\bigl(x+4x\bigr)+d. $$
Suppose a stream of decimal digits enters from left to right. Associate one cell with each binary position. Cell $i$ stores a bit $b_i$ and receives a carry $c_i$ from cell $i-1$.
When a new decimal digit $d$ arrives, the array performs the update
$$ x\leftarrow 10x+d. $$
Write
$$ x=\sum_{i\ge0} b_i2^i. $$
Then
$$ x+4x = \sum_{i\ge0}(b_i+b_{i-2})2^i, $$
where $b_j=0$ for $j<0$. Therefore the coefficient entering position $i$ before carry propagation is
$$ a_i=b_i+b_{i-2}. $$
After multiplication by $2$, the coefficient affecting bit position $i$ becomes
$$ a_{i-1}, $$
and the least significant position also receives the external digit contribution. Thus the local quantity to be reduced at position $i$ is
$$ s_i= a_{i-1}+c_i+\delta_{i0}d, $$
where $\delta_{i0}$ is the Kronecker delta.
Each cell performs
$$ b_i' = s_i \bmod 2, \qquad c_{i+1}=\lfloor s_i/2\rfloor. $$
Since
$$ a_{i-1}\in{0,1,2}, \qquad d\in{0,\ldots,9}, $$
the carries are bounded. At the least significant cell,
$$ s_0\le 2+9=11, $$
so
$$ c_1\le 5. $$
For every higher cell,
$$ s_i\le 2+5=7, $$
hence
$$ c_{i+1}\le 3. $$
Therefore each cell needs only a finite number of states. The update rule is local and independent of the total length of the number.
The resulting array is linear: cell $i$ communicates only with cells $i-1$ and $i+1$. It is iterative: every cell executes the same transition rule. After each decimal digit has entered, a bounded number of additional carry waves suffices to stabilize the representation. Consequently the time required to process an $m$-digit decimal input and produce an $n$-bit binary output is
$$ O(m+n). $$
This is a fast linear iterative array in the sense of Section 4.3.3E.
Verification
Let
$$ y=10x+d. $$
The array computes numbers $b_i'$ and carries $c_{i+1}$ satisfying
$$ s_i=b_i'+2c_{i+1}. $$
Hence
$$ \sum_{i\ge0}s_i2^i = \sum_{i\ge0}b_i'2^i + \sum_{i\ge0}c_{i+1}2^{i+1}. $$
The second sum is exactly the carry contribution generated by the first. Therefore
$$ \sum_{i\ge0}b_i'2^i = \sum_{i\ge0}s_i2^i. $$
Using the definition of $s_i$,
$$ \sum_{i\ge0}s_i2^i = d+ \sum_{i\ge0}a_{i-1}2^i. $$
Since
$$ \sum_{i\ge0}a_{i-1}2^i = 2\sum_{i\ge0}a_i2^i = 2(x+4x) = 10x, $$
we obtain
$$ \sum_{i\ge0}b_i'2^i = 10x+d = y. $$
Thus one pass of the array performs exactly the update required by Method 1b. Repeating this update for the successive decimal digits yields the binary value of the entire input number.
Notes
A closely related construction uses the identity
$$ 10x=(8+2)x, $$
feeding the bit stream simultaneously through shifts by one and three positions and combining the results with local carry propagation. The same asymptotic complexity is obtained. The essential idea is that multiplication by the constant radix $10$ can be realized by a fixed local network, allowing Method 1b to be implemented as a fast linear iterative array.