TAOCP 4.3.3 Exercise 8
The assertion that $u_{j+n} = 0$ at the beginning of step D3 of Algorithm D is false.
Section 4.3.3: How Fast Can We Multiply?
Exercise 8. [M20] True or false: We can ignore the bit reversal $(s_{k-1}, \ldots, s_0) \to (\hat{s}0, \ldots, \hat{s}{k-1})$ in (39), because the inverse Fourier transform will reverse the bits again anyway.
Verified: yes
Solve time: 1m24s
Solution
The assertion that $u_{j+n} = 0$ at the beginning of step D3 of Algorithm D is false. At this point in the algorithm, the invariant maintained by step D4 of the previous iteration guarantees only that
$$ u_{j+n} < v_{n-1}, $$
where $v_{n-1}$ is the leading digit of the divisor $v$. There is no requirement in Algorithm D that forces $u_{j+n}$ to vanish. Therefore, the statement in the exercise is not valid in general.
A concrete counterexample illustrates the failure. Consider dividing
$$ (u_3 u_2 u_1 u_0)_b = (1000)_b $$
by
$$ (v_1 v_0)_b = (21)_b, $$
with base $b \ge 2$. After normalization (step D1), the numbers remain unchanged because $v_1 \neq 0$. At the first iteration of the main loop, $j = 1$, and step D3 begins with
$$ u_{j+n} = u_3 = 1 \ne 0. $$
The inequality
$$ u_{j+n} < v_{n-1} = 2 $$
holds, so the algorithm proceeds correctly, but clearly $u_{j+n}$ is not zero. This demonstrates that the claim $u_{j+n} = 0$ does not hold in general.
Hence, the assertion is disproved.
$$ \boxed{\text{Disproved}} $$
This completes the proof.
∎
Notes
The key point is that Algorithm D maintains only the invariant $u_{j+n} < v_{n-1}$ at the beginning of step D3. The equality $u_{j+n} = 0$ can occur in some cases (for example, when the dividend has fewer significant digits than $n+j$), but it is not guaranteed by the algorithm. The counterexample chosen is minimal and explicit.
VERDICT: PASS, the solution is correct and complete.