TAOCP 7.1.2 Exercise 29

Exercise 29. [M28] [M28] Prove that the text's circuit for sideways addition (27) has depth $O(\log n)$.

Verified: no
Solve time: 10m54s

The missing point in the previous solution is the justification that the block-combining circuit from Exercise 27 has constant depth. We now derive this directly from the structure of that circuit, and only then complete the logarithmic-depth argument.

1. Structure inherited from Exercise 27

In Exercise 27, a number is represented in a sideways form: each bit position is handled independently except for a single controlled transfer of excess weight to the next position. The essential feature of the circuit is that addition is performed using a fixed local transformation at each bit position.

For each bit position $i$, the circuit takes a fixed number of input bits (coming from the two blocks being combined, and possibly a bounded number of auxiliary signals from the representation at that position) and produces:

a new bit for position $i$, and
a carry-like bit that is forwarded to position $i+1$.

This is exactly the structure of a carry-save style transformation, but what matters for depth is more elementary: the transformation at each position is a fixed Boolean function applied uniformly across all positions.

2. Constant-depth implementation of one column

Fix a bit position $i$. The computation performed at this position is a Boolean function of a constant number of inputs. Concretely, it is of the form

$$ (s_i, c_{i+1}) = F(x_i, y_i, z_i), $$

where:

$x_i, y_i$ come from the two blocks being added,
$z_i$ is a bounded auxiliary input determined by the representation (in Exercise 27 this is part of the sideways encoding and is not accumulated through long chains),
$F$ is the full-adder type logic specified by the construction.

The key structural property from Exercise 27 is that:

no bit position depends on carries propagated through a sequence of positions, and
the only interaction between positions is the single-step forwarding of $c_{i+1}$.

Thus each output pair $(s_i, c_{i+1})$ is computed by a fixed finite Boolean network.

A full-adder (or equivalent threshold-of-three function) has constant-depth Boolean implementations using standard bounded fan-in gates. Since $F$ is the same fixed function at every position, its circuit depth is a constant $c$ independent of $n$.

Crucially, the carry signal does not create a sequential dependence chain within the same combining stage. It is computed in parallel and merely routed forward, not processed through repeated logic levels.

Therefore, the entire block-combining operation across all bit positions is a parallel composition of identical constant-depth circuits, which preserves constant depth:

$$ \text{depth(combine)} = O(1). $$

3. Binary-tree structure of sideways addition

The circuit for sideways addition combines $n$ inputs by repeatedly pairing and merging blocks. After each level, the number of active blocks is halved.

Thus the computation forms a binary tree of height

$$ \lceil \log_2 n \rceil. $$

Every path from an input to the output passes through exactly one combining operation per level.

4. Depth recurrence

Let $d(n)$ denote the depth of the circuit on $n$ inputs. Each level performs a constant-depth transformation, so

$$ d(n) \le d(\lceil n/2 \rceil) + c, \quad d(1)=0, $$

where $c$ is the constant depth of the block-combining circuit established above.

Unfolding,

$$ d(n) \le d(\lceil n/2^k \rceil) + kc. $$

Choose $k = \lceil \log_2 n \rceil$, so that $\lceil n/2^k \rceil = 1$. Then

$$ d(n) \le c \lceil \log_2 n \rceil. $$

5. Conclusion

The block-combining circuit is constant depth because each bit position is computed by a fixed bounded-depth Boolean function with no ripple-carry dependency chain. Since the overall circuit applies this operation in a binary-tree structure of height $\Theta(\log n)$, the total depth satisfies

$$ d(n) = O(\log n). $$

This completes the proof. ∎