Content deleted Content added
No edit summary |
|||
Line 1:
'''Booth's multiplication algorithm''' is an [[algorithm]] used to multiply two signed numbers in [[two's complement|two's complement notation]].
The [[algorithm]] was invented by [[Andrew D. Booth]] circa [[1957]] while doing research on [[crystallography]] at [[Birkbeck, University of London|Birkbeck College]] in [[Bloomsbury, London|Bloomsbury]], [[London]]. Booth invented this approach in a quest to find a fast way to multiply numbers with desk calculators as much of his early works involved a great deal of calculations with these devices. In machines of his era, [[shift]]ing was faster than addition, and indeed for some patterns of [[binary number]]s, his algorithm would be faster. Surprisingly the algorithm also works for [[signed number]]s. Booth's algorithm remains to be an interest in the study of [[computer architecture]].▼
==Procedure==
# Convert the [[multiplicator]] to a binary number in [[two's complement]] notation.
# Convert the [[multiplicand]] to a binary number in [[two's complement]] notation.
Line 24 ⟶ 19:
==Example==
We wish to multiply 3 * -4:
Line 49 ⟶ 43:
==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>
Line 58 ⟶ 51:
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.
==
▲The [[algorithm]] was invented by [[Andrew D. Booth]] circa [[1957]] while doing research on [[crystallography]] at [[Birkbeck, University of London|Birkbeck College]] in [[Bloomsbury, London|Bloomsbury]], [[London]]. Booth invented this approach in a quest to find a fast way to multiply numbers with desk calculators as much of his early works involved a great deal of calculations with these devices. In machines of his era, [[shift]]ing was faster than addition, and indeed for some patterns of [[binary number]]s, his algorithm would be faster. Surprisingly the algorithm also works for [[signed number]]s. Booth's algorithm remains to be an interest in the study of [[computer architecture]].
== See also ==
* [[Multiplication ALU]]
==References==
# 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.
| |||