Booth's multiplication algorithm: Difference between revisions

Revision as of 06:29, 23 February 2017

Revision as of 06:30, 23 February 2017

Line 73:

==How it works==

Consider a positive multiplier consisting of a block of 1s surrounded by 0s. For example, 00111110. The product is given by:

: <math> M \times \,^{\prime\prime} 0 \; 0 \; 1 \; 1 \; 1 \; 1 \; 1 \; 0 \,^{\prime\prime} = M \times (2^5 + 2^4 + 2^3 + 2^2 + 2^1) = M \times 62 </math>

:

where M is the multiplicand. The number of operations can be reduced to two by rewriting the same as

: <math> M \times \,^{\prime\prime} 0 \; 1 \; 0 \;0 \;0 \; 0 \mbox{-1} \; 0 \,^{\prime\prime} = M \times (2^6 - 2^1) = M \times 62. </math>

Line 81:

: <math> (\ldots 0 \overbrace{1 \ldots 1}^{n} 0 \ldots)_{2} \equiv (\ldots 1 \overbrace{0 \ldots 0}^{n} 0 \ldots)_{2} - (\ldots 0 \overbrace{0 \ldots 1}^{n} 0 \ldots)_2. </math>

Hence, the multiplication can actually be replaced by the stringsstring of ones in the original number by simpler operations, adding the multiplier, shifting the partial product thus formed by appropriate places, and then finally subtracting the multiplier. It is making use of the fact that it is not necessary to do anything but shift while dealing with 0s in a binary multiplier, and is similar to using the mathematical property that 99&nbsp;=&nbsp;100&nbsp;&minus;&nbsp;1 while multiplying by 99.

This scheme can be extended to any number of blocks of 1s in a multiplier (including the case of a single 1 in a block). Thus,