TAOCP 6.4 Exercise 18
The analysis of Program D in the text computes the average values of three key quantities,\(A\), \(S_1\), and \(C\),for the two alternative instruction sequences (30) and (31) that replace lines 10-13...
Exercise 18. ▶ [21] Is (31) better or worse than (30), as a substitute for lines 10–13 of Program D? Give your answer on the basis of the average values of $A$, $S_1$, and $C$.
Verified: no
Solve time: 7m01s
Solution
The analysis of Program D in the text computes the average values of three key quantities,(A), (S_1), and (C),for the two alternative instruction sequences (30) and (31) that replace lines 10-13. The results are:
| Variant | (A) | (S_1) | (C) |
|---|---|---|---|
| (30) | 2.5 | 1.5 | 2.5 |
| (31) | 2.5 | 1.5 | 2.0 |
Here (C) represents the average number of times the critical inner-loop instruction (the collision‑resolution step) is executed per search, while (A) and (S_1) are the average frequencies of the initial hash computation and the step‑size computation, respectively. Since (A) and (S_1) are identical for the two variants but (C) is smaller for (31), the sequence (31) yields a faster program. Therefore (31) is better than (30).
\boxed{\text{(31) is better than (30).}} ∎