Booth's multiplication algorithm - Wikipedia, the free encyclopedia 01/10/2007 01:42 AM
Booth's multiplication algorithm
From Wikipedia, the free encyclopedia
Booth's multiplication algorithm will multiply two signed binary numbers in two's complement notation.
Contents
1 Procedure
2 Example
3 Why does Booth's algorithm work?
4 History
5 See also
6 References
Procedure
If x is the count of bits of the multiplicand, and y is the count of bits of the multiplier :
Draw a grid of three lines, each with squares for x + y + 1 bits. Label the lines respectively A (add), S
(subtract), and P (product).
In two's complement notation, fill the first x bits of each line with :
A: the multiplicand
S: the negative of the multiplicand
P: zeroes
Fill the next y bits of each line with :
A: zeroes
S: zeroes
P: the multiplier
Fill the last bit of each line with a zero.
Do both of these steps y times :
1 . If the last two bits in the product are...
00 or 11: do nothing.
01: P = P + A. Ignore any overflow.
10: P = P + S. Ignore any overflow.
2 . Arithmetically shift the product right one position.
Drop the last bit from the product for the final result.
http://en.wikipedia.org/wiki/Booth's_multiplication_algorithm Page 1 of 3
Booth's multiplication algorithm - Wikipedia, the free encyclopedia 01/10/2007 01:42 AM
Example
Find 3 × -4:
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. A right shift.
P = 0000 0110 0. The last two bits are 00.
P = 0000 0011 0. A right shift.
P = 0000 0011 0. The last two bits are 10.
P = 1101 0011 0. P = P + S.
P = 1110 1001 1. A right shift.
P = 1110 1001 1. The last two bits are 11.
P = 1111 0100 1. A right shift.
The product is 1111 0100, which is -12.
Why does Booth's algorithm work?
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
The product can be then generated by one addition and one subtraction of the multiplicand. This scheme can be
extended to any number of blocks of 1s in a multiplier (including the case of single 1 in a block). Thus,
Booth's algorithm follows this scheme by performing an addition when it encounters the first digit of a block of ones
(0 1) and a 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.
History
http://en.wikipedia.org/wiki/Booth's_multiplication_algorithm Page 2 of 3
Booth's multiplication algorithm - Wikipedia, the free encyclopedia 01/10/2007 01:42 AM
The algorithm was invented by Andrew D. Booth in 1951 while doing research on crystallography at Birkbeck
College in Bloomsbury, London. Booth used desk calculators that were faster at shifting than adding and created the
algorithm to increase their speed. Booth's algorithm is of interest in the study of computer architecture.
See also
Multiplication ALU
References
1 . Collin, Andrew. Andrew Booth's Computers at Birkbeck College
(http://www.cs.man.ac.uk./CCS/res/res05.htm#e) . Resurrection, Issue 5, Spring 1993. London: Computer
Conservation Society.
2 . Patterson, David and John Hennessy. Computer Organization and Design: The Hardware/Software Interface,
Second Edition. ISBN 1-55860-428-6. San Francisco, California: Morgan Kaufmann Publishers. 1998.
3 . Stallings, William. Computer Organization and Architecture: Designing for performance, Fifth Edition. ISBN
0-13-081294-3. New Jersey: Prentice-Hall, Inc.. 2000.
Retrieved from "http://en.wikipedia.org/wiki/Booth%27s_multiplication_algorithm"
Category: Computer arithmetic
This page was last modified 22:44, 1 January 2007.
All text is available under the terms of the GNU Free Documentation License. (See Copyrights for
details.)
Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc., a US-registered 501(c)(3) tax-
deductible nonprofit charity.
http://en.wikipedia.org/wiki/Booth's_multiplication_algorithm Page 3 of 3
