TAOCP 4.3.1 Exercise 27

We are asked to prove that at the beginning of step D8 in Algorithm D, the unnormalized remainder $(.u_{n-1} \ldots u_1 u_0)_b$ is always an exact multiple of the divisor $d$.

taocpmathematicsalgorithmsvolume-2math-medium

Section 4.3.1: The Classical Algorithms

Exercise 27. [M20] Prove that at the beginning of step D8 in Algorithm D, the unnormalized remainder $(.u_{n-1} \ldots u_1 u_0)_b$ is always an exact multiple of $d$.

Verified: no
Solve time: 2m17s

Solution

We are asked to prove that at the beginning of step D8 in Algorithm D, the unnormalized remainder

$(.u_{n-1} \ldots u_1 u_0)_b$

is always an exact multiple of the divisor $d$. We proceed using the notation and structure of Algorithm D as given in Section 4.3.1.

Algorithm D performs division of an $(m+n)$-place integer $(u_{m+n-1} \ldots u_0)b$ by an $n$-place integer $(v{n-1} \ldots v_0)_b$, producing an $(m+1)$-place quotient $(q_m \ldots q_0)_b$ and an $n$-place remainder. Step D8 is the final correction step, where we check for an overshoot in the estimate of the quotient digit and adjust both the quotient and the remainder.

Let us denote by $d$ the normalized divisor:

$d = v_{n-1}b^{n-1} + \cdots + v_1 b + v_0.$

We need to show that just before D8 is executed for any quotient digit $q_j$, the unnormalized remainder

$r_j = (.u_{n-1} \ldots u_0)_b$

satisfies

$r_j = k \cdot d$

for some integer $k$.

Step 1: Structure of Algorithm D

By the construction of Algorithm D (Section 4.3.1), at the beginning of D8 we have already executed the following steps for the current quotient digit $q_j$:

  1. We computed an estimated quotient digit $\hat{q}_j$ using the most significant digits of the remainder:

$\hat{q}j = \left\lfloor \frac{u{n+j} b + u_{n+j-1}}{v_{n-1}} \right\rfloor.$ 2. We performed the subtraction of the corresponding multiple of the divisor:

$(.u_{n+j} \ldots u_j)b \leftarrow (.u{n+j} \ldots u_j)_b - \hat{q}_j \cdot d.$ 3. If the subtraction caused a negative remainder, we adjusted $\hat{q}_j$ downward, increasing the remainder by exactly $d$ each time until it became nonnegative.

At this stage, the remainder after step D7 is either nonnegative and less than $b \cdot d$, or negative but corrected in D8.

Step 2: Inductive Invariant

We claim the following invariant holds at the beginning of D8 for any quotient digit $q_j$:

The unnormalized remainder $r_j = (.u_{n-1} \ldots u_0)_b$ is an integer multiple of the divisor $d$.

We prove this by induction on $j$.

Base case ($j=0$): Before the first quotient digit is computed, the remainder equals the original dividend $(u_{m+n-1} \ldots u_0)_b$. By the definition of step D1, the dividend can be expressed as

$(u_{m+n-1} \ldots u_0)_b = q_0 \cdot d + r_0,$

where $r_0$ is initially zero in the unnormalized remainder. Hence $r_0$ is a multiple of $d$ (specifically $0 \cdot d$).

Inductive step: Assume the invariant holds for $j-1$, i.e., the remainder before computing $q_j$ is a multiple of $d$:

$r_{j-1} = k \cdot d$

for some integer $k$. In step D7, we subtract $\hat{q}j \cdot d$ from $r{j-1}$:

$r_j = r_{j-1} - \hat{q}_j \cdot d = (k - \hat{q}_j) \cdot d.$

Thus $r_j$ remains an integer multiple of $d$. Any subsequent adjustments in D8 consist of adding $d$ repeatedly until $r_j \ge 0$, which preserves divisibility by $d$.

By induction, this invariant holds for all $j$.

Step 3: Conclusion

The argument shows that, at the beginning of D8, the unnormalized remainder $(.u_{n-1} \ldots u_0)_b$ is always of the form

$r_j = k \cdot d$

for some integer $k$. Therefore, it is an exact multiple of the divisor $d$. The key is that each operation in Algorithm D either subtracts or adds integer multiples of $d$, and the initial remainder is a multiple of $d$ by construction. This completes the proof.

∎