Booth's multiplication algorithm is a
multiplication algorithm
A multiplication algorithm is an algorithm (or method) to multiply two numbers. Depending on the size of the numbers, different algorithms are more efficient than others. Efficient multiplication algorithms have existed since the advent of the d ...
that multiplies two signed
binary
Binary may refer to:
Science and technology Mathematics
* Binary number, a representation of numbers using only two digits (0 and 1)
* Binary function, a function that takes two arguments
* Binary operation, a mathematical operation that ta ...
numbers in
two's complement notation
Two's complement is a mathematical operation to reversibly convert a positive binary number into a negative binary number with equivalent (but negative) value, using the binary digit with the greatest place value (the leftmost bit in big- endian ...
. The
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
was invented by
in 1950 while doing research on
crystallography at
Birkbeck College in
Bloomsbury,
London
London is the capital and List of urban areas in the United Kingdom, largest city of England and the United Kingdom, with a population of just under 9 million. It stands on the River Thames in south-east England at the head of a estuary dow ...
.
Booth's algorithm is of interest in the study of
computer architecture
In computer engineering, computer architecture is a description of the structure of a computer system made from component parts. It can sometimes be a high-level description that ignores details of the implementation. At a more detailed level, the ...
.
The algorithm
Booth's algorithm examines adjacent pairs of
bit
The bit is the most basic unit of information in computing and digital communications. The name is a portmanteau of binary digit. The bit represents a logical state with one of two possible values. These values are most commonly represente ...
s of the 'N'-bit multiplier ''Y'' in signed
two's complement
Two's complement is a mathematical operation to reversibly convert a positive binary number into a negative binary number with equivalent (but negative) value, using the binary digit with the greatest place value (the leftmost bit in big- endian ...
representation, including an implicit bit below the
least significant bit, ''y''
−1 = 0. For each bit ''y''
''i'', for ''i'' running from 0 to ''N'' − 1, the bits ''y''
''i'' and ''y''
''i''−1 are considered. Where these two bits are equal, the product accumulator ''P'' is left unchanged. Where ''y''
''i'' = 0 and ''y''
''i''−1 = 1, the multiplicand times 2
''i'' is added to ''P''; and where ''y''
i = 1 and ''y''
i−1 = 0, the multiplicand times 2
''i'' is subtracted from ''P''. The final value of ''P'' is the signed product.
The representations of the multiplicand and product are not specified; typically, these are both also in two's complement representation, like the multiplier, but any number system that supports addition and subtraction will work as well. As stated here, the order of the steps is not determined. Typically, it proceeds from
LSB to
MSB, starting at ''i'' = 0; the multiplication by 2
''i'' is then typically replaced by incremental shifting of the ''P'' accumulator to the right between steps; low bits can be shifted out, and subsequent additions and subtractions can then be done just on the highest ''N'' bits of ''P''.
There are many variations and optimizations on these details.
The algorithm is often described as converting strings of 1s in the multiplier to a high-order +1 and a low-order −1 at the ends of the string. When a string runs through the MSB, there is no high-order +1, and the net effect is interpretation as a negative of the appropriate value.
A typical implementation
Booth's algorithm can be implemented by repeatedly adding (with ordinary unsigned binary addition) one of two predetermined values ''A'' and ''S'' to a product ''P'', then performing a rightward
arithmetic shift
In computer programming, an arithmetic shift is a shift operator, sometimes termed a signed shift (though it is not restricted to signed operands). The two basic types are the arithmetic left shift and the arithmetic right shift. For binary ...
on ''P''. Let m and r be the
multiplicand
Multiplication (often denoted by the cross symbol , by the mid-line dot operator , by juxtaposition, or, on computers, by an asterisk ) is one of the four elementary mathematical operations of arithmetic, with the other ones being additio ...
and
multiplier, respectively; and let ''x'' and ''y'' represent the number of bits in m and r.
# Determine the values of ''A'' and ''S'', and the initial value of ''P''. All of these numbers should have a length equal to (''x'' + ''y'' + 1).
## A: Fill the most significant (leftmost) bits with the value of m. Fill the remaining (''y'' + 1) bits with zeros.
## S: Fill the most significant bits with the value of (−m) in two's complement notation. Fill the remaining (''y'' + 1) bits with zeros.
## P: Fill the most significant ''x'' bits with zeros. To the right of this, append the value of r. Fill the least significant (rightmost) bit with a zero.
# Determine the two least significant (rightmost) bits of ''P''.
## If they are 01, find the value of ''P'' + ''A''. Ignore any overflow.
## If they are 10, find the value of ''P'' + ''S''. Ignore any overflow.
## If they are 00, do nothing. Use ''P'' directly in the next step.
## If they are 11, do nothing. Use ''P'' directly in the next step.
#
Arithmetically shift the value obtained in the 2nd step by a single place to the right. Let ''P'' now equal this new value.
# Repeat steps 2 and 3 until they have been done ''y'' times.
# Drop the least significant (rightmost) bit from ''P''. This is the product of m and r.
Example
Find 3 × (−4), with m = 3 and r = −4, and ''x'' = 4 and ''y'' = 4:
* m = 0011, -m = 1101, r = 1100
* A = 0011 0000 0
* S = 1101 0000 0
* P = 0000 1100 0
* Perform the loop four times:
*# P = 0000 1100 0. The last two bits are 00.
*#* P = 0000 0110 0. Arithmetic right shift.
*# P = 0000 0110 0. The last two bits are 00.
*#* P = 0000 0011 0. Arithmetic right shift.
*# P = 0000 0011 0. The last two bits are 10.
*#* P = 1101 0011 0. P = P + S.
*#* P = 1110 1001 1. Arithmetic right shift.
*# P = 1110 1001 1. The last two bits are 11.
*#* P = 1111 0100 1. Arithmetic right shift.
* The product is 1111 0100, which is −12.
The above-mentioned technique is inadequate when the multiplicand is the
most negative number that can be represented (e.g. if the multiplicand has 4 bits then this value is −8). This is because then an overflow occurs when computing -m, the negation of the multiplicand, which is needed in order to set S. One possible correction to this problem is to extend A, S, and P by one bit each, while they still represent the same number. That is, while −8 was previously represented in four bits by 1000, it is now represented in 5 bits by 1 1000. This then follows the implementation described above, with modifications in determining the bits of A and S; e.g., the value of m, originally assigned to the first ''x'' bits of A, will be now be extended to ''x''+1 bits and assigned to the first ''x''+1 bits of A. Below, the improved technique is demonstrated by multiplying −8 by 2 using 4 bits for the multiplicand and the multiplier:
* A = 1 1000 0000 0
* S = 0 1000 0000 0
* P = 0 0000 0010 0
* Perform the loop four times:
*# P = 0 0000 0010 0. The last two bits are 00.
*#* P = 0 0000 0001 0. Right shift.
*# P = 0 0000 0001 0. The last two bits are 10.
*#* P = 0 1000 0001 0. P = P + S.
*#* P = 0 0100 0000 1. Right shift.
*# P = 0 0100 0000 1. The last two bits are 01.
*#* P = 1 1100 0000 1. P = P + A.
*#* P = 1 1110 0000 0. Right shift.
*# P = 1 1110 0000 0. The last two bits are 00.
*#* P = 1 1111 0000 0. Right shift.
* The product is 11110000 (after discarding the first and the last bit) which is −16.
How it works
Consider a positive multiplier consisting of a block of 1s surrounded by 0s. For example, 00111110. The product is given by:
:
where M is the multiplicand. The number of operations can be reduced to two by rewriting the same as
:
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:
:
Hence, the multiplication can actually be replaced by the string 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 = 100 − 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,
:
:
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
*
Binary multiplier
A binary multiplier is an electronic circuit used in digital electronics, such as a computer, to multiply two binary numbers.
A variety of computer arithmetic techniques can be used to implement a digital multiplier. Most techniques involve comp ...
*
Non-adjacent form
*
Redundant binary representation
*
Wallace tree
A Wallace multiplier is a hardware implementation of a binary multiplier, a digital circuit that multiplies two integers. It uses a selection of full and half adders (the Wallace tree or Wallace reduction) to sum partial products in stages unti ...
*
Dadda multiplier
The Dadda multiplier is a hardware binary multiplier design invented by computer scientist Luigi Dadda in 1965. It uses a selection of full and half adders to sum the partial products in stages (the Dadda tree or Dadda reduction) until two numbers ...
References
Further reading
*
*
*
* {{cite web , title=Advanced Arithmetic Techniques , author-first=John J. G. , author-last=Savard , date=2018 , orig-year=2006 , work=quadibloc , url=http://www.quadibloc.com/comp/cp0202.htm , access-date=2018-07-16 , url-status=live , archive-url=https://web.archive.org/web/20180703001722/http://www.quadibloc.com/comp/cp0202.htm , archive-date=2018-07-03
External links
Radix-4 Booth Encodingi
A Formal Theory of RTL and Computer ArithmeticBooth's Algorithm JavaScript Simulator
1950 introductions
1950 in London
1950 in science
Binary arithmetic
Computer arithmetic algorithms
Multiplication
Birkbeck, University of London