Content deleted Content added
Why does Booth's Algorithm work ? |
|||
Line 47:
1111 0100 in two's complement = -(00001011+1) = -(00001100) = -12
==Why does Booth's Algorithm work ?==
Consider a positive multiplicator consisting of a block of 1s surrounded by 0s. For example, 00111110. The product is given by:
:<math>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 (2^6 - 2^1) </math>
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 multiplicator (including the case of single 1 in a block). Thus,
:<math> M \times (00111010) = M \times (2^5 + 2^4 + 2^3 + 2^1) = M \times (2^5 - 2^3 + 2^2 - 2^1) </math>
Booth's algorithm follows this scheme by performing a subtraction when it encounters the first 1 of a block (1-0) and an addition when it encounters the end of the block (0-1). This works for a negative multiplicator as well. For the same reason, the Booth's algorithm performs fewer additions and subtraction than a normal multiplication algorithm in most cases.
== See also ==
Line 56 ⟶ 66:
# Collin, Andrew. [http://www.cs.man.ac.uk/CCS/res/res05.htm Andrew Booth's Computers at Birkbeck College]. ''Resurrection'', Issue 5, Spring 1993. London: ''Computer Conservation Society''.
# Patterson, David and John Hennessy. <u>Computer Organization and Design: The Hardware/Software Interface, Second Edition.</u> ISBN 1558604286. San Francisco, California: ''Morgan Kaufmann Publishers''. 1998.
# Stallings, William. <u>Computer Organization and Architecture: Designing for performance, Fifth Edition.</u> ISBN 0130812943. New Jersey: ''Prentice-Hall, Inc.''. 2000.
[[Category:Number theoretic algorithms]]
[[Category:Computer arithmetic]]
| |||