next up previous
Next: Signed Multiplication Up: arithmetic_html Previous: Fast Addition

Multiplication and Division

Multiplication

Example for multiplication:


\begin{displaymath}13 \times 11 =143 \end{displaymath}

The paper-and-pencel method:


\begin{displaymath}\begin{tabular}{cccccccc}
& & & & 1 & 1 & 0 & 1 \\
& & & x...
... & & &  \hline
1 & 0 & 0 & 0 & 1 & 1 & 1 & 1
\end{tabular} \end{displaymath}

Improve the method so that only 2 numbers are added each time:


\begin{displaymath}\begin{tabular}{cccccccc}
& & & & 1 & 1 & 0 & 1 \\
& & & x...
... & & &  \hline
1 & 0 & 0 & 0 & 1 & 1 & 1 & 1
\end{tabular} \end{displaymath}

multiplication_hardware.gif

Algorithm for hardware multiplication

Do n times:

{

if ($q_0=1$) then $A \leftarrow A + M$;

right shift A and Q by 1 bit

}

Note: When A and Q are right shifted, the MSB of A is filled with 0 and the LSB of A becomes the MSB of Q, and the LSB of Q is lost.

Example:

\begin{displaymath}13 \times 11 =143 \end{displaymath}

Always use three registers M, A, and Q. Initially, the multiplicand $13=(1101)_2$ is in M, the multiplier $11=(1011)_2$ is in Q, and A is zero.

\begin{displaymath}
\begin{tabular}{l\vert cccc} \hline
& [M] & 1101 & & \\
&...
...\\
right shift A/Q & 0 & 1000 & & 1111  \hline
\end{tabular}\end{displaymath}

The upper half of the product $(010001111)_2=143$ is in register A, while the lower half is in register Q.

Example for division:


\begin{displaymath}274\div 13=21\frac{1}{13} \end{displaymath}

binary_divide.gif

division_hardware.gif

Algorithm for hardware division (restoring)

Do n times:

{ left shift A and Q by 1 bit

$A \leftarrow A - M$;

if $A < 0$ ($a_{n-1}=1$), then $q_0 \leftarrow 0$, $A \leftarrow A + M$ (restore)

else $q_0 \leftarrow 1$

}

Note: When A and Q are left shifted, the MSB of Q becomes the LSB of A, and the MSB of A is lost. The LSB of Q is made available for the next quotient bit.

Example:

\begin{displaymath}8 \div 3=2\frac{2}{3} \end{displaymath}

Initially, the divisor $3=(0011)_2$ is in register M, the dividend $8=(1000)_2$ is in register Q, and register A is zero. Note that subtraction by $3=(0011)_2$ is implemented by adding its 2's complement $1101$.

\begin{displaymath}
\begin{tabular}{l\vert cccc} \hline
& [M] & 0011 & & \\
&...
... & & \\
& & 0010 & & \underline{0010}  \hline
\end{tabular}\end{displaymath}

The quotient $(0010)_2=2$ is in register Q, and the reminder $(0010)_2=2$ is in register A.

Algorithm for hardware division (non-restoring)

In the algorithm above, if the subtraction produces a non-positive result ($A>0$), registers A and Q are left shifted and the next subtraction is carried out. But if the subtraction produces a negative result ($A < 0$), the dividend need be first restored by adding the divisor back before left shift A and Q and the next subtraction:

Note that when $A < 0$, the restoration is avoided by combining the two steps. This leads to a faster non-restoring division algorithm:

Algorithm for hardware division (non-restoring)

Do n times:

{ left shift A and Q by 1 bit

if (previous $A\ge 0$) then $A \leftarrow A - M$

else $A \leftarrow A + M$;

if (current $A\ge 0$) then $q_0 \leftarrow 1$

else $q_0 \leftarrow 0$

}

if ($A < 0$) then $A \leftarrow A + M$ (remainder must be positive)

non_restoring_div.gif

The quotient $(0010)_2=2$ is in register Q, and the reminder $(0010)_2=2$ is in register A. The restoring division requires two operations (subtraction followed by an addition to restore) for each zero in the quotient. But non-restoring division only requires one operation (either addition or subtraction) for each bit in quotient.


next up previous
Next: Signed Multiplication Up: arithmetic_html Previous: Fast Addition
Ruye Wang 2013-01-25