Booth's multiplication algorithm: Difference between revisions

Revision as of 10:44, 9 November 2021

Revision as of 01:32, 2 December 2021

Line 66:

: <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 \; 0 \; 0 \mbox{-1} \; 0 \,; ^{\prime\prime} = 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 80:

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.

== See also ==