Booth's multiplication algorithm: Difference between revisions

Revision as of 02:47, 9 October 2005

Revision as of 03:23, 9 October 2005

Line 2:

==Procedure==

* For later reference, write the multiplicand and its negative in [[two's complement]] notation. write :

** A = (the multiplicand).

** S = (the negative of the multiplicand).

** Count how many bits are in the multiplier. Write that many 0s to the right of A, then to the right of S.

** Add a 0 to the right of A, then to the right of S.

* Write the starting product :

** Count how many bits are in the multiplicand. Write that many 0s.

** To the right of the zeroes, write the multiplier.

** To the right of the multiplier, write a 0.

* A, S, and the product should all have the same count of digits.

* Count how many bits are in the multiplier. That many times, do these two steps :

*# If the two rightmost bits in the product are...

*#* 00 or 11: do nothing.

*#* 01: add the multiplicandA to the far left of the product. Ignore any overflow.

*#* 10: add the negative of the multiplicandS to the far left of the product. Ignore any overflow.

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