TAOCP 4.3.3 Exercise 11
Let the linear iterative array be the family of automata M_0,M_1,M_2,\ldots defined by equations (37) and (38).
Section 4.3.3: How Fast Can We Multiply?
Exercise 11. ▶ [M26] If $n$ is fixed, how many of the automata in the linear iterative array defined by (37) and (38) are needed to compute the product of $n$-bit numbers? (Notice that the automaton $M_j$ is influenced only by the component $z_j^i$ of the machine on its right, so we may remove all automata whose $z_0$ component is always zero whenever the inputs are $n$-bit numbers.)
Verified: yes
Solve time: 3m11s
Setup
Let the linear iterative array be the family of automata
$$ M_0,M_1,M_2,\ldots $$
defined by equations (37) and (38). The state of $M_j$ at time $i$ contains a component $z_j^i$, and the exercise states that $M_j$ is influenced only by the component $z_j^i$ of the machine on its right.
We must determine, for fixed $n$, how many automata are actually needed in order to multiply two $n$-bit numbers. The point is that every automaton whose $z_0$-component remains permanently zero may be omitted.
The multiplication of two $n$-bit numbers produces a product having at most $2n$ bits. Hence only finitely many diagonals of the computation can contribute nonzero information.
Solution
Let
$$ u=(u_{n-1}\ldots u_0)2,\qquad v=(v{n-1}\ldots v_0)_2 $$
be $n$-bit numbers. Thus
$$ u_i=v_i=0\qquad\text{for }i\ge n. $$
In the linear iterative array, the automaton $M_j$ is responsible for information associated with the $j$th diagonal of the multiplication process. The only external influence on $M_j$ comes from the quantity $z_j^i$ produced by the automaton immediately to its right.
For binary multiplication, the contribution to the product bit of weight $2^j$ arises from pairs
$$ (u_a,v_b) $$
with
$$ a+b=j. $$
Since
$$ 0\le a\le n-1,\qquad 0\le b\le n-1, $$
the largest possible value of $a+b$ is
$$ (n-1)+(n-1)=2n-2. $$
Therefore no partial product can ever contribute to diagonals $j\ge 2n-1$. For every automaton $M_j$ with
$$ j\ge 2n-1, $$
all inputs affecting its $z$-component are identically zero throughout the computation. Hence
$$ z_j^i=0 \qquad\text{for all }i, $$
and such automata never influence any automaton to their left.
Consequently all automata
$$ M_{2n-1},M_{2n},M_{2n+1},\ldots $$
may be removed.
On the other hand, for each index
$$ 0\le j\le 2n-2, $$
there exist indices $a,b$ with
$$ 0\le a,b\le n-1,\qquad a+b=j. $$
Indeed,
$$ a=j,\ b=0 \quad\text{when }0\le j\le n-1, $$
and
$$ a=n-1,\ b=j-(n-1) \quad\text{when }n\le j\le 2n-2. $$
Thus each diagonal $j\le 2n-2$ can receive a nonzero contribution for suitable inputs. Hence none of the automata
$$ M_0,M_1,\ldots,M_{2n-2} $$
can be omitted in general.
The required number of automata is therefore
$$ (2n-2)-0+1=2n-1. $$
Hence exactly
$$ \boxed{2n-1} $$
automata are needed to compute the product of two $n$-bit numbers.
Verification
The product of two $n$-bit numbers satisfies
$$ 0\le uv < 2^n\cdot 2^n = 2^{2n}, $$
so the product contains at most $2n$ bits, namely positions
$$ 0,1,\ldots,2n-1. $$
The highest nonzero partial-product diagonal occurs at
$$ (n-1)+(n-1)=2n-2. $$
Therefore the active diagonals are precisely
$$ 0,1,\ldots,2n-2, $$
which correspond to
$$ 2n-1 $$
automata.
This completes the proof.
∎