Booth's multiplication algorithm: Difference between revisions

Revision as of 06:28, 23 February 2017

Revision as of 06:29, 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>