TAOCP 4.3.1 Exercise 16
Let U=(.
Section 4.3.1: The Classical Algorithms
Exercise 16. [39] (Short division.) Design an algorithm that divides a nonnegative $n$-place integer $(.u_1 u_2 \ldots u_n)b$ by $v$, where $v$ is a single-precision number (that is, $0 < v < b$), producing the quotient $(.w{n-1} \ldots w_1 w_0)_b$ and remainder $r$.
Verified: yes
Solve time: 1m29s
Setup
Let
$$ U=(.u_1u_2\cdots u_n)_b, \qquad 0<v<b, $$
where each digit satisfies $0\le u_j<b$.
Since
$$ (.u_1u_2\cdots u_n)_b =\frac{(u_1u_2\cdots u_n)_b}{b^n}, $$
the problem is equivalent to dividing the integer
$$ (u_1u_2\cdots u_n)_b $$
by the single-precision integer $v$, and expressing the quotient in the form
$$ (.w_1w_2\cdots w_n)_b $$
together with a remainder $r$ satisfying $0\le r<v$.
The primitive operation $\alpha_3$ divides a two-place integer by a one-place integer and yields a one-place quotient and remainder. The algorithm should therefore proceed from the most significant digit toward the least significant digit, exactly as in ordinary short division.
Solution
Algorithm D (Short division.)
D1. [Initialize.] Set $j\leftarrow1$ and $r\leftarrow0$.
D2. [Form partial dividend.] Set
$$ t\leftarrow rb+u_j . $$
Since $0\le r<v<b$, we have
$$ 0\le t<(v-1)b+(b-1)=vb-1< b^2, $$
so $t$ is a valid two-place integer.
D3. [Divide.] Divide $t$ by $v$, obtaining
$$ w_j\leftarrow \left\lfloor\frac{t}{v}\right\rfloor, \qquad r\leftarrow t\bmod v. $$
Because $t<vb$, the quotient satisfies
$$ 0\le w_j<b, $$
hence $w_j$ is a valid radix-$b$ digit.
D4. [Loop on $j$.] Increase $j$ by one. If $j\le n$, return to step D2. Otherwise terminate.
The output is
$$ (.w_1w_2\cdots w_n)_b $$
together with remainder $r$.
Verification
For $1\le j\le n$, define
$$ U_j=(u_1u_2\cdots u_j)_b, \qquad W_j=(w_1w_2\cdots w_j)_b . $$
The inductive assertion is
$$ U_j=vW_j+r, \qquad 0\le r<v, $$
after the $j$th execution of step D3.
For $j=1$, step D2 forms
$$ t=u_1, $$
and step D3 gives
$$ u_1=vw_1+r, \qquad 0\le r<v. $$
Hence
$$ U_1=vW_1+r. $$
Assume
$$ U_j=vW_j+r, \qquad 0\le r<v, $$
holds after processing digit $u_j$.
At the next stage,
$$ t=rb+u_{j+1}. $$
Step D3 computes digits satisfying
$$ t=vw_{j+1}+r', \qquad 0\le r'<v. $$
Multiplying the induction hypothesis by $b$ and adding $u_{j+1}$ gives
$$ U_{j+1} =bU_j+u_{j+1} =b(vW_j+r)+u_{j+1}. $$
Substituting $rb+u_{j+1}=vw_{j+1}+r'$ yields
$$ U_{j+1} =v(bW_j+w_{j+1})+r'. $$
Since
$$ bW_j+w_{j+1}=W_{j+1}, $$
we obtain
$$ U_{j+1}=vW_{j+1}+r', \qquad 0\le r'<v. $$
Therefore the assertion is preserved.
After the final iteration,
$$ (u_1u_2\cdots u_n)_b = v(w_1w_2\cdots w_n)_b+r, \qquad 0\le r<v. $$
Dividing by $b^n$ gives
$$ (.u_1u_2\cdots u_n)_b = v(.w_1w_2\cdots w_n)_b+\frac{r}{b^n}, \qquad 0\le r<v. $$
Thus $(.w_1w_2\cdots w_n)_b$ is the quotient and $r$ is the remainder. This completes the proof.
∎
Notes
Each iteration performs exactly one application of the primitive operation $\alpha_3$. Hence the algorithm requires $n$ single-precision divisions and processes the digits from left to right, exactly as in ordinary pencil-and-paper short division.
The final answer is
$$ \boxed{ (u_1u_2\cdots u_n)_b = v(w_1w_2\cdots w_n)_b+r, \quad 0\le r<v } $$
or equivalently,
$$ \boxed{ (.u_1u_2\cdots u_n)_b = v(.w_1w_2\cdots w_n)_b+\frac{r}{b^n}. } $$