TAOCP 4.3.1 Exercise 29

Section 4.3.1: The Classical Algorithms

Exercise 29. [**] [15] Prove or disprove: At the beginning of step D3 of Algorithm D, we always have $u_{j+n} = 0$.

Verified: no
Solve time: 2m04s

The statement is false. At the beginning of step D3, Algorithm D guarantees only that

$u_{j+n} < v_{n-1};$

this is the invariant established by the previous iteration and maintained by step D4. Nothing in the algorithm forces $u_{j+n}$ to vanish.

A counterexample occurs when dividing

$(u_3u_2u_1u_0)_b=(1000)_b$

by

$(v_1v_0)_b=(21)_b,$

with $b\ge2$. After normalization, no change occurs. At the first pass, $j=1$, and step D3 begins with

$u_{j+n}=u_3=1\ne0.$

Since $v_{n-1}=2$, the required condition $u_{j+n}<v_{n-1}$ is satisfied, but $u_{j+n}$ is not zero. Therefore the assertion fails in general.

$$ \boxed{\text{Disproved}} $$