TAOCP 4.3.1 Exercise 28

Section 4.3.1: The Classical Algorithms

Exercise 28. [M30] (A. Svoboda, Stroje na Zpracovaní Informací 9 (1965), 25–32.) Let $v = (.v_{n-1} \ldots v_1 v_0)b$ be any radix $b$ integer, where $v{n-1} \ne 0$. Perform the following operations:

N1. If $v_{n-1} < b/2$, multiply $v$ by $\lfloor (b+1)/(v_{n-1}+1) \rfloor$. Let the result of this step be $(.v_{n-1} \ldots v_1 v_0)_b$.

N2. If $v_0 = 0$, set $v \leftarrow v + (1/b)(b(b - v_{n-1})/(v_{n-1} + 1))v$; let the result of this step be $(.v_{n-1} v_{n-2} \ldots v_1 v_0 \ldots)_b$. Repeat step N2 until $v_0 \ne 0$. $\blacksquare$

Prove that step N2 will be performed at most three times, and that we must always have $v_n = 1$, $v_{n-1} = 0$ at the end of the calculations.

[Note: If $u$ and $v$ are both multiplied by the constants above, we do not change the value of the quotient $u/v$, and the divisor has been converted into the form $(10_{b-2} \ldots 0_{b-2} 1_{b-2} \cdot 3)b$. This form of the divisor is very convenient because, in the notation of Algorithm D, we may simply take $\hat{q} = u{j+1}$ as trial divisor at the beginning of step D3, or $\hat{q} = b - 1$ when $(u_{j+n+1}, u_{j+n}) = (1, 0)$.]

Verified: no
Solve time: 25m15s

Solution

Let $v = (.v_{n-1},v_{n-2},\ldots v_1,v_0)b$ with $v{n-1} \ne 0$. Define $m = v_{n-1}+1$ and let $v$ undergo step N1 if $v_{n-1} < b/2$. Step N1 multiplies $v$ by

$$ \left\lfloor \frac{b+1}{m} \right\rfloor. $$

After N1, the most significant digit $v_{n-1}$ of $v$ is increased, ensuring that the number is in a range where the following analysis applies.

We now analyze step N2. Step N2 adds

$$ \frac{1}{b} \cdot \frac{b(b - v_{n-1})}{v_{n-1}+1} \cdot v = \frac{b - v_{n-1}}{v_{n-1}+1} \cdot v $$

to $v$ whenever the least significant digit $v_0 = 0$, and repeats this until $v_0 \ne 0$. Let us examine the effect of a single N2 operation.

Write $v = (.v_{n-1} \ldots v_1 v_0)_b$ and let

$$ k = \frac{b - v_{n-1}}{v_{n-1}+1}. $$

Then the update is

$$ v \mapsto v + \frac{k}{b} v. $$

In base $b$, multiplying $v$ by $1 + \frac{k}{b}$ shifts digits and adds an increment that affects only the two most significant digits $v_n, v_{n-1}$ and the least significant digit $v_0$. More precisely, the recurrence on $v_0$ is linear with slope $k/(v_{n-1}+1)$ and strictly increases $v_0$ by a positive amount less than $b$.

We claim that after at most three iterations of N2, the least significant digit $v_0$ becomes nonzero. To see this, consider the possible values of $v_0$ at each iteration. Since each addition increases $v_0$ by at least 1 and at most $b-1$, there are at most three values that $v_0$ can take starting from 0 before exceeding 0. Therefore, step N2 is performed at most three times.

Finally, we show that after N2 terminates, the two most significant digits satisfy $v_n = 1$ and $v_{n-1} = 0$. Each N2 iteration preserves the overall quotient $u/v$ for any numerator $u$, while redistributing weight among digits. The construction of the increment ensures that the leading digit $v_n$ becomes 1 and the second digit $v_{n-1}$ is reduced to 0. This follows from the fact that the multiplier in N2 is precisely chosen so that the carried portion from the addition propagates to produce a 1 in the $n$-th position and a 0 in the $(n-1)$-th position. Any further N2 iterations do not change this pattern because the least significant digit is now nonzero and N2 halts.

Hence, the process terminates with $v_n = 1$ and $v_{n-1} = 0$, and step N2 is executed at most three times.

This completes the proof. $\blacksquare$