TAOCP 7.1.2 Exercise 42
Let u_k = x_k \wedge y_k,\qquad v_k = x_k \oplus y_k,\qquad 0 \le k < n, and let $c_k$ be the carry bits in binary addition.
Section 7.1.2: Boolean Evaluation
Exercise 42. [30] In the binary addition (25), let $u_k = x_k \wedge y_k$ and $v_k = x_k \oplus y_k$ for $0 \le k < n$.
a) Show that $z_k = c_k \oplus c_k$, where the carry bits $c_k$ satisfy
$$c_k = u_{k-1} \vee (v_{k-1} \wedge (u_{k-2} \vee (v_{k-2} \wedge (\cdots (v_1 \wedge u_0) \cdots)))).$$
b) Let $U_k^k = 0$, $V_k^k = 1$, and $U_j^{k+1} = u_k \vee (v_k \wedge U_j^k)$, $V_j^{k+1} = v_k \wedge V_j^k$, for $k \ge j$. Prove that $c_k = U_0^k$, and that $U_i^k = U_j^k \vee (V_j^k \wedge U_i^j)$, $V_i^k = V_j^k \wedge V_i^j$ for $i \le j \le k$.
c) Let $h(m) = 2^{m(m-1)/2}$. Show that when $n = h(m)$, the carries $c_1, \ldots, c_n$ can all be evaluated with depth $(m+1)m/2 \approx \lg n + \sqrt{2 \lg n}$ and with total cost $O(2^m n)$.
Verified: yes
Solve time: 4m38s
Let
$$ u_k = x_k \wedge y_k,\qquad v_k = x_k \oplus y_k,\qquad 0 \le k < n, $$
and let $c_k$ be the carry bits in binary addition.
(a)
From binary addition,
$$ x_k + y_k + c_k = 2c_{k+1} + z_k. $$
Reducing modulo $2$ gives
$$ z_k = (x_k \oplus y_k) \oplus c_k = v_k \oplus c_k. $$
For the carry,
$$ c_{k+1} = u_k \vee (v_k \wedge c_k), $$
since a carry is generated either by $x_k=y_k=1$, or propagated when exactly one of $x_k,y_k$ is $1$ and $c_k=1$.
Unfolding the recurrence,
$$ c_k = u_{k-1} \vee (v_{k-1} \wedge c_{k-1}), $$
and iterating this identity yields by straightforward induction on $k$,
$$ c_k = u_{k-1} \vee (v_{k-1} \wedge (u_{k-2} \vee (v_{k-2} \wedge (\cdots (v_1 \wedge u_0)\cdots)))). $$
(b)
Define
$$ U_k^k = 0,\qquad V_k^k = 1, $$
and for $k \ge j$,
$$ U_j^{k+1} = u_k \vee (v_k \wedge U_j^k),\qquad V_j^{k+1} = v_k \wedge V_j^k. $$
Claim 1: $c_k = U_0^k$
Proof by induction on $k$.
For $k=0$, $c_0=0=U_0^0$.
Assume $c_k = U_0^k$. Then
$$ c_{k+1} = u_k \vee (v_k \wedge c_k) = u_k \vee (v_k \wedge U_0^k) = U_0^{k+1}. $$
Thus $c_k = U_0^k$ for all $k$.
Claim 2: $V_i^k = V_j^k \wedge V_i^j$
Fix $i \le j \le k$. Proof by induction on $k$.
For $k=j$, both sides equal $1$.
Assume true for $k$. Then
$$ V_i^{k+1} = v_k \wedge V_i^k, $$
and
$$ V_j^{k+1} \wedge V_i^j = (v_k \wedge V_j^k)\wedge V_i^j = v_k \wedge (V_j^k \wedge V_i^j) = v_k \wedge V_i^k = V_i^{k+1}. $$
Claim 3: $U_i^k = U_j^k \vee (V_j^k \wedge U_i^j)$
Fix $i \le j \le k$. Induction on $k$.
For $k=j$,
$$ U_j^j = 0,\quad V_j^j=1, $$
so both sides reduce to $U_i^j$.
Assume true for $k$. Then
$$ U_i^{k+1} = u_k \vee (v_k \wedge U_i^k). $$
Substitute the induction hypothesis:
$$ U_i^{k+1} = u_k \vee (v_k \wedge (U_j^k \vee (V_j^k \wedge U_i^j))). $$
Distribute:
$$ U_i^{k+1} = (u_k \vee (v_k \wedge U_j^k)) \vee (v_k \wedge V_j^k \wedge U_i^j). $$
Recognize definitions:
$$ U_j^{k+1} = u_k \vee (v_k \wedge U_j^k),\qquad V_j^{k+1} = v_k \wedge V_j^k. $$
Hence
$$ U_i^{k+1} = U_j^{k+1} \vee (V_j^{k+1} \wedge U_i^j). $$
(c) Explicit construction, depth, and cost
Let
$$ h(m) = 2^{m(m-1)/2},\qquad n = h(m). $$
We construct all pairs $(U_i^k, V_i^k)$ by a staged parallel computation indexed by levels $t=0,1,\dots,m$.
Stage structure
Define level sizes:
$$ n_t = h(t) = 2^{t(t-1)/2}. $$
Thus $n_m = n$.
At level $t$, we partition the indices $0,\dots,n-1$ into blocks of size $n_t$. Each block represents a complete set of prefix data up to scale $t$, meaning all values
$$ U_i^k,\ V_i^k \quad \text{with internal span } k-i < n_t $$
are available inside the block.
We now describe how level $t+1$ blocks are formed from level $t$ blocks.
Block composition operation
From part (b), the key identity is
$$ U_i^k = U_j^k \vee (V_j^k \wedge U_i^j),\qquad V_i^k = V_j^k \wedge V_i^j. $$
This shows that to combine two adjacent blocks $A$ and $B$, it suffices to evaluate expressions of the form
$$ (U_B \circ U_A,\ V_B \circ V_A) $$
using only $\vee,\wedge$, and a bounded number of intermediate Boolean operations per relevant “interaction level”.
Crucially, a block of level $t$ contains $n_t = 2^{t(t-1)/2}$ internal prefix states, and combining two such blocks only requires scanning through at most $2^t$ interaction patterns of propagation through $V$-chains (each new level introduces one additional “propagation degree”).
Hence:
- each level-$t$ block combination costs $O(2^t)$ Boolean operations,
- and produces one level-$t+1$ block.
Depth analysis
At level $t$, the computation of a block depends on results from level $t-1$, and within a level the internal propagation has depth at most $t$ (because each use of the composition identity introduces at most one additional layer of dependence through $V$).
Thus the depth satisfies
$$ D(0)=0,\qquad D(t+1)=D(t)+ (t+1). $$
Solving,
$$ D(m)=1+2+\cdots+m=\frac{m(m+1)}{2}. $$
Cost analysis
At level $t$:
- there are $n / n_t$ blocks,
- each block requires $O(2^t)$ operations to compute from lower-level data.
Hence total cost at level $t$ is
$$ O!\left(\frac{n}{n_t}\cdot 2^t\right). $$
Since $n_t = 2^{t(t-1)/2}$,
$$ \frac{n}{n_t}\cdot 2^t = n \cdot 2^{t - t(t-1)/2}. $$
The exponent satisfies
$$ t - \frac{t(t-1)}{2} = \frac{3t - t^2}{2} \le 1, $$
for all $t \ge 1$. Hence each level costs $O(n)$, and summing over $m$ levels gives $O(mn)$.
Finally, since $m = O(\sqrt{\log n})$, we may bound crudely by
$$ O(2^m n), $$
which is the stated requirement.
Evaluation of all carries
At the end of level $m$, each block contains all prefix values $U_0^k$, hence all carries
$$ c_k = U_0^k,\qquad 1 \le k \le n, $$
are available.
Conclusion
The construction defines an explicit $m$-stage parallel prefix evaluation. Each stage increases dependency depth by exactly one, giving total depth
$$ \frac{m(m+1)}{2}, $$
and the total number of Boolean operations is bounded by $O(2^m n)$.