TAOCP 7.1.3 Exercise 123
The previous argument fails because “dependency width” was not defined in a way that is stable under the actual word operations.
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 123. [M23] [M23] Let aq be the constant 1 + 2q + 22q + · · · + 2(q−1)q = (2q2 −1)/(2q −1). Using (104), show that there are infinitely many q such that the operation of multiplying by aq, modulo 2q2, requires Ω(log q) steps in any n-bit broadword chain with n ≥q2.
Verified: no
Solve time: 3m56s
The previous argument fails because “dependency width” was not defined in a way that is stable under the actual word operations. The correct way to formalize the intuition is to track sets of influencing input blocks and show that these sets can grow only by bounded union at each operation.
1. Model of computation
We use the standard broadword chain model from TAOCP: we compute from the input word $x$ using a finite sequence of $n$-bit words
$$ y^{(0)} = x,\quad y^{(1)},\dots,y^{(t)} = x a_q, $$
where each $y^{(s+1)}$ is obtained from previously computed words by one of the allowed broadword operations (bitwise Boolean operations, shifts by fixed amounts, addition, subtraction, and multiplication). Each operation has constant arity (two inputs for binary operations; shifts use one input).
Partition each $n$-bit word into $q$ blocks of $q$ bits:
$$ x = x_{q-1}\cdots x_1 x_0,\qquad 0 \le x_i < 2^q. $$
2. Dependency sets (correct definition)
For each intermediate word $y$ and each block index $i$, define the dependency set
$$ S(y,i) \subseteq {0,1,\dots,q-1} $$
as the set of input block indices $j$ such that some bit of $x_j$ can influence block $y_i$.
Formally, this is defined inductively:
- For the input:
$$ S(x,i) = {i}. $$
- For any operation $y = F(u,v)$, define
$$ S(y,i) \subseteq \bigcup_{k} S(u,k)\ \cup\ \bigcup_{\ell} S(v,\ell), $$
where the unions range over those block indices $k,\ell$ whose bits can affect output block $i$ through the fixed word operation $F$.
This is justified because every bit of every allowed operation is a fixed Boolean function of the corresponding input bits; hence no new dependencies can be created except by merging those already present in the operands.
For shifts, indices are merely relabeled, so dependency sets are permuted but not enlarged.
3. Block span measure
Define the span
$$ \operatorname{sp}(y,i) = \max S(y,i) - \min S(y,i) + 1, $$
and the global span
$$ W(y) = \max_i \operatorname{sp}(y,i). $$
Initially,
$$ W(x) = 1. $$
4. Closure properties of span
We bound how span evolves under each allowed operation.
Lemma 1 (Boolean operations)
If $y = u \ \mathrm{op}\ v$ where op is any bitwise Boolean operation, then
$$ W(y) \le \max(W(u), W(v)). $$
Reason: each output bit depends only on corresponding input bits; no cross-block interaction is introduced.
Lemma 2 (Addition and subtraction)
If $y = u \pm v$, then
$$ W(y) \le W(u) + W(v). $$
Reason: addition may propagate carries, but any output block depends only on bits of the two operands; thus its dependency set is contained in the union of the dependency sets of corresponding blocks of $u$ and $v$, giving additive growth of span.
Lemma 3 (Multiplication)
If $y = u \cdot v$, then using (104) (block convolution structure),
each output block $y_i$ depends only on pairs $(u_j, v_k)$ with $j+k=i$. Hence
$$ W(y) \le W(u) + W(v). $$
Reason: any input block influencing $y_i$ must influence either some $u_j$ or some $v_k$ with $j+k=i$, so indices can expand by at most addition of spans.
Lemma 4 (Shifts)
Shifts by fixed amounts permute block indices, so
$$ W(y) = W(u). $$
Corollary (one-step growth bound)
Every allowed operation $F$ satisfies
$$ W(F(u,v)) \le W(u) + W(v). $$
Since each step uses only constantly many previously computed words, we obtain the worst-case recurrence
$$ W(y^{(s+1)}) \le 2, W(y^{(s)}). $$
Hence
$$ W(y^{(t)}) \le 2^t. $$
This replaces the incorrect informal “dependency width doubling” argument with a precise inductive bound on span growth.
5. Span required by multiplication by $a_q$
Recall
$$ a_q = 1 + 2^q + 2^{2q} + \cdots + 2^{(q-1)q}. $$
Thus multiplication by $a_q$ gives
$$ x a_q = x + (x \ll q) + (x \ll 2q) + \cdots + (x \ll (q-1)q). $$
In block form, this implies
$$ (xa_q)i = \sum{j=0}^{i} x_j \pmod{2^q}. $$
Therefore every block $i$ depends on all blocks $0,1,\dots,i$. In particular,
$$ S(xa_q, i) = {0,1,\dots,i}. $$
Hence
$$ W(xa_q) = q. $$
This is exact: block $q-1$ depends on all $q$ input blocks.
6. Lower bound on chain length
If a chain computes $xa_q$ in $t$ steps, then by the growth bound,
$$ q = W(xa_q) \le W(y^{(t)}) \le 2^t. $$
Thus
$$ t \ge \log_2 q. $$
7. Conclusion
For every $q$,
$$ \text{any broadword chain computing multiplication by } a_q \text{ requires } \Omega(\log q) \text{ steps}. $$
Hence there are infinitely many such $q$, completing the proof. ∎