Booth's multiplication algorithm: Difference between revisions

Revision as of 03:26, 9 October 2005

Revision as of 03:45, 9 October 2005

Line 2:

==Procedure==

If ''x'' is the number of bits of the multiplicand, and ''y'' is the number of bits of the multiplier :

* For later reference, 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.

* Draw a grid with three rows and x + y + 1 columns. Label them respectively A (add), S (subtract), and P (product).

* Write the starting product :

* In [[two's complement notation]], fill the first ''x'' bits of each line with :

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

** A: = (the multiplicand).

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

** ToS: the rightnegative of the multiplier, write a 0multiplicand.

** P: zeroes.

* A, S, andFill the productnext should''y'' allbits haveof theeach sameline count ofwith digits.:

** A: zeroes.

** S: zeroes.

** P: the multiplier.

* Fill the final bit of each line with zeroes.

* 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: addP A= toP the+ productA. Ignore any overflow.

*#* 10: addP S= toP the+ productS. Ignore any overflow.

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

* RemoveDrop the rightmost bit from the product for the final result.

==Example==