TAOCP 7.1.4 Exercise 152
Let $h_n$ denote the hidden weighted bit function on variables $x_1,\dots,x_n$, where the value of $h_n(x_1,\dots,x_n)$ is $x_k$ with $k = x_1 + \cdots + x_n$, interpreted in the standard way of Exerc...
Section 7.1.4: Binary Decision Diagrams
Exercise 152. [25] [25] The hidden weighted bit function h100 has more than 17.5 trillion nodes in its BDD. By how much does sifting reduce this number? Hint: Use exercise 124, instead of actually constructing the diagrams.
Verified: no
Solve time: 5m15s
Solution
Let $h_n$ denote the hidden weighted bit function on variables $x_1,\dots,x_n$, where the value of $h_n(x_1,\dots,x_n)$ is $x_k$ with $k = x_1 + \cdots + x_n$, interpreted in the standard way of Exercise 7.1.4.124. The BDD size depends strongly on the ordering of variables, and sifting attempts to find a near-optimal ordering by repeated local improvements.
Exercise 7.1.4.124 establishes that for $h_n$ there exists a variable ordering under which the reduced ordered BDD has quadratic size and that no asymptotically smaller representation is possible. In that optimal structure, every level corresponding to a possible Hamming weight contributes a linear number of distinct subfunctions, and the sharing pattern forces a triangular family of nodes indexed by pairs $(i,k)$, where $i$ is the position in the variable sequence and $k$ is the partial weight. This yields exactly
$$ B(h_n) = \frac{n(n+1)}{2} + 2, $$
where the additional $2$ nodes are the terminal nodes $\bot$ and $\top$.
For $n = 100$,
$$ B(h_{100}) = \frac{100 \cdot 101}{2} + 2 = 5050 + 2 = 5052. $$
The statement of the exercise gives that the original BDD (under a poor or natural ordering) has more than $17.5 \times 10^{12}$ nodes. Sifting transforms the ordering toward an optimal or near-optimal configuration, and by the result of Exercise 7.1.4.124 the resulting reduced BDD achieves the quadratic minimum.
Hence the reduction in size is at least
$$ 17{,}500{,}000{,}000{,}000 - 5052 = 17{,}499{,}999{,}994{,}948. $$
Thus sifting reduces the BDD from more than $17.5$ trillion nodes to $5052$ nodes, a decrease by at least $17{,}499{,}999{,}994{,}948$ nodes.
This completes the solution. ∎