Content deleted Content added
Reverted 2 edits by 27.251.158.66 (talk): MOS:HEAD and uniformity. (TW) |
|||
Line 1:
'''Booth's multiplication algorithm''' is a [[multiplication algorithm]] that multiplies two signed [[base 2|binary]] numbers in [[two's complement|two's complement notation]]. The [[algorithm]] was invented by [[Andrew Donald Booth]] in 1950 while doing research on [[crystallography]] at [[Birkbeck, University of London|Birkbeck College]] in [[Bloomsbury]], [[London]]. Booth used desk calculators that were faster at [[Arithmetic shift|shift]]ing than adding and created the algorithm to increase their speed. Booth's algorithm is of interest in the study of [[computer architecture]].
==The
Booth's algorithm examines adjacent pairs of [[bit]]s of the ''N''-bit multiplier ''Y'' in signed [[two's complement]] representation, including an implicit bit below the [[least significant bit]], ''y''<sub>−1</sub> = 0. For each bit ''y''<sub>''i''</sub>, for ''i'' running from 0 to ''N'' − 1, the bits ''y''<sub>''i''</sub> and ''y''<sub>''i''−1</sub> are considered. Where these two bits are equal, the product accumulator ''P'' is left unchanged. Where ''y''<sub>''i''</sub> = 0 and ''y''<sub>''i''−1</sub> = 1, the multiplicand times 2<sup>''i''</sup> is added to ''P''; and where ''y''<sub>i</sub> = 1 and ''y''<sub>i−1</sub> = 0, the multiplicand times 2<sup>''i''</sup> is subtracted from ''P''. The final value of ''P'' is the signed product.
Line 66:
*# P = 0 0100 000'''0 1'''. The last two bits are 01.
*#* P = 1 1100 0000 1. P = P + A.
*#* P = 1 1110 0000 0.
*# P = 1 1110 000'''0 0'''. The last two bits are 00.
*#* P = 1 1111 0000 0. Right shift.
| |||