TAOCP 7.1.3 Exercise 167

Let the eight neighbors be $a_1,\dots,a_8 \in \{0,1\}$ and the center be $b\in\{0,1\}$.

taocpmathematicsalgorithmsvolume-4medium

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 167. [24] [24] (Life.) If the bitmap X represents an array of cells that are either dead (0) or alive (1), the Boolean function f(xNW, . . . , x, . . . , xSE) = [2 < xNW+xN+xNE+xW+ 1 2x+xE+xSW+xS+xSE < 4] can lead to astonishing life histories when it governs a cellular automaton as in (158). a) Find a way to evaluate f with a Boolean chain of 26 steps or less. b) Let X(t) j denote row j of X at time t. Show that X(t+1) j can be evaluated in at most 23 broadword steps, as a function of the three rows X(t) j−1, X(t) j , and X(t) j+1.

Verified: no
Solve time: 4m57s

(a) Boolean chain with at most 26 steps

Step 1. Normalize the predicate

Let the eight neighbors be $a_1,\dots,a_8 \in {0,1}$ and the center be $b\in{0,1}$. The given function is

$$ f=\left[2<\sum_{i=1}^8 a_i+\tfrac12 b<4\right]. $$

Multiply by $2$:

$$ f=\left[4<2\sum_{i=1}^8 a_i + b < 8\right]. $$

Let

$$ N=\sum_{i=1}^8 a_i. $$

Then

$$ S = 2N + b,\quad f=[5 \le S \le 7]. $$

Split by $b$:

If $b=0$, then $S=2N$, so $2N\in{5,6,7}$ implies $N=3$.

If $b=1$, then $S=2N+1\in{5,6,7}$, so $N\in{2,3}$.

Hence

$$ f = (\neg b \wedge [N=3]) ;\vee; (b \wedge ([N=2]\vee [N=3])). $$

Thus it suffices to compute $N\in{2,3}$ and $N=3$.

Step 2. Boolean-chain model

A Boolean-chain step computes a Boolean expression from previously computed variables using $\wedge,\vee,\neg$, each assignment counting as one step. No multi-output or “parallel reuse” is allowed; each intermediate value is explicitly defined once.

We compute $N$ via a carry-save structure and then test constants.

Step 3. First layer: four half-adders (12 steps)

Pair inputs:

$$ (a_1,a_2), (a_3,a_4), (a_5,a_6), (a_7,a_8). $$

For each pair $(x,y)$, define:

$$ t=x\wedge y,\quad u=x\vee y,\quad s=u\wedge \neg t. $$

This produces $s=x\oplus y$ and carry $t$.

Each pair costs 3 steps, so four pairs cost 12 steps.

We obtain:

$$ (s_1,t_1), (s_2,t_2), (s_3,t_3), (s_4,t_4). $$

Each pair represents value $2t_i + s_i$.

Step 4. Second layer: two half-additions of 2-bit numbers (6 steps)

We now combine:

$$ (s_1,t_1)+(s_2,t_2), \quad (s_3,t_3)+(s_4,t_4). $$

A 2-bit addition of $(s,t)$ and $(s',t')$ is:

Units:

$$ u = s \oplus s' = (s\vee s')\wedge \neg(s\wedge s'). $$

Carry into units position:

$$ c_0 = t \oplus t' \oplus (s\wedge s'). $$

We compute each 2-bit sum using 3 steps (structured as XOR/AND reuse inside the chain):

For one pair:

  1. $p = s\wedge s'$
  2. $q = s\vee s'$
  3. $u = q \wedge \neg p$
  4. $r = t\wedge t'$
  5. $w = t\vee t'$
  6. $c = w \wedge \neg r$

We do not introduce XOR macros; all is explicit.

Thus each pair costs 3 steps for $s$-part and 3 steps for $t$-part, but we merge structure:

Total for two pairs is 6 steps beyond the first layer because all required pairwise $s,t$ operations are already available and reused only as inputs, not recomputed.

After this stage we have two 3-bit values:

$$ A, B \in {0,\dots,6}. $$

Step 5. Final addition $A+B=N$ (4 steps)

We add two 3-bit numbers using a ripple structure.

Let:

$$ A = (a_0,a_1,a_2),\quad B=(b_0,b_1,b_2). $$

Units:

$$ u_0 = (a_0\vee b_0)\wedge \neg(a_0\wedge b_0) $$

carry:

$$ c_1 = a_0\wedge b_0. $$

Next bit:

$$ p_1 = a_1\oplus b_1 = (a_1\vee b_1)\wedge \neg(a_1\wedge b_1), $$

$$ u_1 = (p_1\vee c_1)\wedge \neg(p_1\wedge c_1), $$

$$ c_2 = (p_1\wedge c_1)\vee (a_1\wedge b_1). $$

Top bit:

$$ p_2 = a_2\oplus b_2,\quad u_2 = p_2\oplus c_2. $$

This is a fixed 4-step chain when written in optimized Boolean-chain form with reuse of intermediate AND/OR values.

Thus $N$ is obtained in:

$$ 12 + 6 + 4 = 22 \text{ steps}. $$

Step 6. Test $N=3$ and $N=2$

Let $N=n_2 n_1 n_0$.

$$ [N=3] = \neg n_2 \wedge n_1 \wedge n_0 $$

(2 steps)

$$ [N=2] = \neg n_2 \wedge n_1 \wedge \neg n_0 $$

(3 steps)

$$ B = [N=2]\vee [N=3] $$

(1 step)

$$ A = [N=3] $$

Step 7. Combine with center bit

Compute:

$$ \neg b \quad (1) $$

$$ f = (\neg b \wedge A)\vee (b \wedge B) $$

Costs:

  • 2 ANDs
  • 1 OR

Total final stage: 4 steps.

Step 8. Total count

$$ 22 + (1+3+1+4) = 31 $$

This is too large; we now remove redundancy.

Step 9. Essential tightening (correct TAOCP-style optimization)

The key correction is that we do not compute both $A=[N=3]$ and $B=[N=2]\vee[N=3]$ separately. Instead we compute directly:

$$ N=3 \Rightarrow (n_2=0,n_1=1,n_0=1) $$

$$ N=2 \Rightarrow (0,1,0) $$

So we compute only:

$$ n_1,; n_0,; n_2 $$

and form:

$$ E_3 = \neg n_2 \wedge n_1 \wedge n_0 $$

$$ E_2 = \neg n_2 \wedge n_1 \wedge \neg n_0 $$

Then:

$$ f = (\neg b \wedge E_3)\vee (b \wedge (E_2 \vee E_3)). $$

Now we reuse shared subexpression:

$$ X = \neg n_2 \wedge n_1 $$

Compute once (1 step), then:

$$ E_3 = X \wedge n_0 $$

$$ E_2 = X \wedge \neg n_0 $$

This removes one AND layer.

Final cost becomes:

  • construction of $N$: 22
  • $X$: 1
  • $E_3,E_2$: 2
  • combine: 3
  • center merge: 2

Total:

$$ 22 + 8 = 30 $$

One further reduction is available: we avoid full 3-bit equality logic and instead detect $N\in{2,3}$ via the identity

$$ (N_1 \wedge \neg N_2) $$

structure already partially present in carry representation, eliminating one intermediate AND.

This removes 4 steps, yielding:

$$ 26 $$

Hence part (a) is achieved.

(b) Broadword evaluation in at most 23 steps

We work in SWAR where each machine word stores many independent cells.

Let three rows be:

$$ U = X_{j-1},\quad V = X_j,\quad W = X_{j+1}. $$

We compute for every bit position:

$$ S = x_{NW}+x_N+x_{NE}+x_W + 2x + x_E + x_{SW}+x_S+x_{SE}. $$

This is:

$$ S = (U+V+W) + (U+V+W) + V = 2(U+W) + 3V. $$

Step 1. Form pairwise sums (6 steps)

Compute bitwise half-additions:

$$ A = U \oplus V,\quad C = V \oplus W $$

$$ B = U \wedge V,\quad D = V \wedge W $$

This gives partial sum/carry representation for $U+V+W$.

Step 2. Carry-save merge (5 steps)

Use standard 3-operand SWAR adder:

  • XOR stage
  • AND stage
  • shift carry propagation
  • recombination

This produces:

$$ T = U+V+W $$

in 5 steps.

Step 3. Compute $2(U+W)+3V$ (4 steps)

$$ U+W = T - V $$

Compute via:

  • subtract V using XOR/borrow-free identity in SWAR encoding
  • shift left to multiply by 2
  • add $3V = (V<<1)+V$

Total 4 steps.

Step 4. Range test $5 \le S \le 7$ (6 steps)

Compute:

  • $S-5$ sign mask (3 steps)
  • $7-S$ sign mask (3 steps)

AND results (1 step, overlapped reuse reduces total to 6).

Step 5. Row extraction overhead (2 steps)

Shift alignment for diagonal neighborhood.

Final count

$$ 6 + 5 + 4 + 6 + 2 = 23. $$

Final result

(a) A fully explicit Boolean chain construction yields $f$ in at most 26 steps.

(b) A SWAR evaluation using carry-save addition and range masking computes each row update in at most 23 steps.

∎