Booth's multiplication algorithm: Difference between revisions

Revision as of 01:59, 9 October 2005

Revision as of 02:07, 9 October 2005

Line 4:

* Convert the factors to [[two's complement]] notation.

* Find the negative of the multiplicand.

* The product starts out as the multiplier.
* Count how many bits are in the multiplicand. Add that many 0s to the left of the multiplierproduct, to make room for the additions below.

* Add a 0 to the right of the multiplierproduct.

* Count how many bits are in the multiplierproduct. That many times, do this :

*# If the two rightmost bits are...

*#* 00 or 11: do nothing.

*#* 01: add the multiplicand to the far left of the multiplierproduct. Ignore any overflow.

*#* 10: add the negative of the multiplicand to the far left of the multiplierproduct. Ignore any overflow.

*# Perform a right [[arithmetic shift]] on the result.

* Remove the rightmost bit from the multiplicandproduct.

==Example==