How to find quotient at each step in binary division for hardware implementation?

Question

The division principle is simply \$D = Q \cdot V + R\$, where \$D\$ is a dividend, \$V\$ is a divisor, \$Q\$ is a quotient and \$R\$ is a remainder.

The pen-and-paper binary division algorithm works like this:

Example: Divide \100110ドル\$ by \101ドル\$.

I prefer the conversion to polynomials and divide that way:

\$(x+1) | (x^3 + x^2 + 1)\$.

The remainder is \1ドル\$, and the quotient is \$x^2\$.

Converted to binary: \$Q = 100\$, \$R = 001\$.

Now, the partial remainder is defined as \$R_{i+1} = R_i - q_i \cdot 2^{-i} \cdot V\$.

While I don't really understand how this was derived, I understand what it means: it suggests the next partial remainder is the previous remainder subtracted by the right-shifted divisor.

Note that I am studying from John P. Hayes’ Computer Organization and Architecture textbook.

The central problem in division is finding the quotient digit \$q_i\$. If radix-\$r\$ numbers are being represented, then \$q_i\$ must be chosen from among \$r\$ possible values. When \$r=2\$, \$q_i\$ can be generated by comparing \$V\$ and \2ドルR_i\$ in the \$i\$th step...

If \$V > 2R_i\$, then \$q_i = 0\$; otherwise, \$q_i = 1\$. If \$V\$ is long, a combinational magnitude comparator circuit may be impractical, in which case \$q_i\$ is usually determined by subtracting \$V\$ from \2ドルR_i\$ and examining the sign of \$(2R_i - V)\$. If the sign of \$(2R_i - V)\$ is negative, \$q_i = 0\$; otherwise, \$q_i = 1\$.

I must say Hayes is a fantastic author. I love reading textbooks that I cannot understand the first time, second time, third time... and only understand on the \$n\$th time. However, a little bit of extra explanation would be lovely.

• periblepsis: The book's notation showing the partial remainder recurrence is incorrect. Figure 4.21 proves this fact. Do you need further explanation?
• Ghungroo: Yup, I'd love explanation.(if that's fair)

Answer 1

In general, we can say that:

$$\begin{align*} D&=\sum_{i=0}^{n-1} 2^i,円d_i \\\\ V&=\sum_{i=0}^{m-1} 2^i,円v_i \end{align*}$$

where \$n=6\$ is the number of binary bits required for \$D\$, assuming the most significant bit is 1, and where \$m=3\$ is the number of binary bits required for \$V\$, assuming the most significant bit is 1.

The author then shifts \$V\$ by \$n-m\$ bit positions prior to the operation. So:

$$\begin{align*} V^{'}&=2^{n-m} V =2^{n-m}\sum_{i=0}^{m-1} 2^i,円v_i \end{align*}$$

Okay. Let's set up the recurrences for Figure 4.21:

$$\begin{align*} R_0&=D&q_{_3}&=\left\{\begin{array}\0,円&2^{0},円V^{'}\gt D\1,円&2^{0},円V^{'}\le D\end{array}\right. \\\\ R_1&=R_0-q_{_3},2円^{0},円V^{'}&q_{_2}&=\left\{\begin{array}\0,円&2^{-1},円V^{'}\gt R_1\1,円&2^{-1},円V^{'}\le R_1\end{array}\right. \\\\ R_2&=R_1-q_{_2},2円^{-1},円V^{'}&q_{_1}&=\left\{\begin{array}\0,円&2^{-2},円V^{'}\gt R_2\1,円&2^{-2},円V^{'}\le R_2\end{array}\right. \\\\ R_3&=R_2-q_{_1},2円^{-2},円V^{'}&q_{_0}&=\left\{\begin{array}\0,円&2^{-3},円V^{'}\gt R_3\1,円&2^{-3},円V^{'}\le R_3\end{array}\right. \\\\ R_4&=R_3-q_{_0},2円^{-3},円V^{'} \end{align*}$$

(Note that the indices increase moving down for \$R\$ while the indices decrease while moving down for \$q\$. This is inconsistent with equation 4.28)

Or, using the actual values of \$D=100110\$ and \$V=101\$ (or \$V^{'}=101000\$):

$$\begin{align*} R_0&=100110&q_{_3}&=\left\{\begin{array}\0,円&\text{as }101000\gt 100110\end{array}\right. \\\\ R_1&=100110-0=100110&q_{_2}&=\left\{\begin{array}\1,円&\text{as }10100\le 100110\end{array}\right. \\\\ R_2&=100110-ひく10100=わ10010&q_{_1}&=\left\{\begin{array}\1,円&\text{as }1010\le 10010\end{array}\right. \\\\ R_3&=10010-1010=1000&q_{_0}&=\left\{\begin{array}\1,円&\text{as }101\le 1000\end{array}\right. \\\\ R_4&=1000-101=011 \end{align*}$$

From this you can already see that equation 4.28, which is actually a recurrence, might be:

$$\begin{align*} R_{0}&=D&W_0&=V^{'} &q_{n-m}&=\left\{\begin{array}\0,円&W_0\gt R_0\1,円&W_0\le R_0\end{array}\right. \\\\ R_{i}&=R_{i-1}-q_{_{n-m-i+1}},円W_{i-1}&W_i&=\left\lfloor \frac12 W_{i-1}\right\rfloor &q_{n-m-i}&=\left\{\begin{array}\0,円&W_i\gt R_{i}\1,円&W_i\le R_{i}\end{array}\right. \\\\ R_{n-m+1}&=R_{n-m}-q_{_{0}},円W_{n-m} \end{align*}$$

where \0ドル\lt i\le n-m\$.

And that doesn't match up with the text, even if you take a moment to adjust my use of \$i\$ vs the author's use. Their recurrence has \$R_i\$ with \$i\$ increasing, just as in their steps in Figure 4.21. But unlike Figure 4.21 where \$q_i\$ has \$i\$ decreasing in their steps. So there just has to be an error of some kind in equation 4.28. The indices don't match up in direction (or value, unless accidentally.)

Recurrences are often difficult to put into a provable closed form. There's a whole subfield explored in a book called Concrete Mathematics by Ronald L. Graham, Donald E. Knuth & Oren Patashnik.

Final note: Your textbook author also covers non-restoring division, which is important to learn about. But his Figure 4.23, which very commonly found in the literature (and discussed in some detail in this not-bad video on a non-restoring usage), can be substantially simplified without any loss of results. The number of register bits can be reduced as is shown well in a division block illustration found in the User Manual for the ADSP-21xx family DSP processors.