TAOCP 7.1.4 Exercise 68

Exercise 68. [20] [20] Speed up step S10 by streamlining the common case when LEFT(t) < 0.

Verified: no
Solve time: 5m48s

Solution

Step S10 of Algorithm S is entered when a newly constructed or retrieved node $t$ has a negative pointer in its LEFT field, indicating that the node represents a terminal value rather than an internal branch node in the reduced ordered BDD representation. In this encoding, negative pointers correspond to sink nodes, so $LEFT(t) < 0$ identifies that the left argument of the current apply step is already a constant $\bot$ or $\top$.

In the unoptimized formulation, step S10 proceeds by treating this situation uniformly with the general node-combination mechanism: it continues the standard recursive or table-driven construction of the result node, even though no further decomposition of the left argument is possible. This introduces unnecessary overhead, since the value of the Boolean operation is already determined at the level of terminal cases.

The optimization replaces this general handling by an immediate evaluation of the Boolean operator at the sink level. Let $u = LEFT(t)$ and $v = RIGHT(t)$. Since $u < 0$, both $u$ and $v$ are interpreted as elements of ${\bot, \top}$ via the standard encoding used in the BDD representation. The result of applying the operation associated with Algorithm S, denoted $\circ$, to $u$ and $v$ is therefore a single Boolean value in ${\bot, \top}$.

Instead of proceeding with node creation logic, step S10 can return the canonical sink node representing this value directly. This bypasses all further apply recursion and eliminates any need to consult or update the unique table for internal nodes, since no internal node is generated in this case.

Thus the streamlined version of step S10 is to compute $u \circ v$ using a constant-time lookup on the four possible pairs $(\bot,\bot)$, $(\bot,\top)$, $(\top,\bot)$, $(\top,\top)$, and immediately return the corresponding sink node. This reduces the common terminal-handling case from a general BDD node construction step to a single constant-time table access followed by a direct return, preserving correctness because terminal operands admit no further decomposition under the Shannon expansion used by Algorithm S.

This completes the solution. ∎