Content deleted Content added
m →The algorithm: Removed invisible unicode characters + other fixes, replaced: → (2) using AWB (12020) |
Petri Krohn (talk | contribs) |
||
Line 2:
==The algorithm==
[[Image:Calculator walther hg.jpg|thumb|right|A Walther WSR160 [[Odhner Arithmometer|arithmometer]] from 1960. Each turn of the crank handle adds ''(up)'' or subtracts ''(down)'' the operand set to the top register from the value in the accumulator register at the bottom. Shifting the adder left or right multiplies the effect by ten.]]
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.
| |||
