Booth's multiplication algorithm: Difference between revisions

Revision as of 17:51, 3 March 2025

Revision as of 06:37, 4 March 2025

Line 65:

==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 display="block"> M \times \,^begin{\prime\primearray}{|r|r|r|r|r|r|r|r|}\hline 0 \;& 0 \;& 1 \;& 1 \;& 1 \;& 1 \;& 1 \;& 0 \,^{\prime \primehline \end{array} = 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 display="block"> M \times \,^begin{\prime\primearray}{|r|r|r|r|r|r|r|r|}\hline 0 \;& 1 \; & 0 \;& 0 \;& 0 \;& 0 \mbox{& -1} \;& 0 \\; ^{\primehline \primeend{array} = M \times (2^6 - 2^1) = M \times 62. </math>

In fact, it can be shown that any sequence of 1s in a binary number can be broken into the difference of two binary numbers:

Line 77:

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,

<math display="block"> M \times \,^begin{\prime\primearray}{|r|r|r|r|r|r|r|r|}\hline 0 \;& 0 \;& 1 \;& 1 \;& 1 \;& 0 \;& 1 \;& 0 \,^{\prime \primehline \end{array}\ = M \times (2^5 + 2^4 + 2^3 + 2^1) = M \times 58 </math>

<math display="block"> M \times \,^begin{\prime\primearray}{|r|r|r|r|r|r|r|r|}\hline 0 \;& 1 \;& 0 \;& 0 \mbox{& -1} \;& 1 \mbox{& -1} \;& 0 \,^{\prime \primehline \end{array} = M \times (2^6 - 2^3 + 2^2 - 2^1) = M \times 58. </math>

Booth's algorithm follows this old scheme by performing an addition when it encounters the first digit of a block of ones (0 1) and subtraction when it encounters the end of the block (1 0). This works for a negative multiplier as well. When the ones in a multiplier are grouped into long blocks, Booth's algorithm performs fewer additions and subtractions than the normal multiplication algorithm.