Booth's multiplication algorithm: Difference between revisions

Revision as of 01:26, 9 October 2005

Revision as of 01:33, 9 October 2005

Line 2:

==Procedure==

#* Convert the factors to [[two's complement]] notation. Find the negative of the multiplicand.

#* AddCount 0show tomany thebits leftare ofin the multipliermultiplicand. in aAdd quantitythat equivalentmany 0s to the numberleft of bits in the multiplicandmultiplier.

#* Add a 0 to the right of the binary number that results from the previous stepmultiplier.

# Check the two rightmost bits of the resultant binary number:

*Repeat these two steps for each bit in the multiplier :

#* 00 or 11: do nothing.

*# CheckIf the two rightmost bits of the resultant binary number:are...

#* 01: add the multiplicand to the left half of the binary number. Ignore any carry or overflow.

*#* 00 or 11: do nothing.

#* 10: subtract the multiplicand to the left half of the binary number. Ignore any carry or overflow.

*#* 01: add the multiplicand to the left half of the binary numbermultiplier. Ignore any carry or overflow.

# Perform an right [[arithmetic shift]] on the result.

*#* Repeat10: stepadd 4the andnegative 5of asthe manymultiplicand timesto asthe thereleft arehalf bits inof the multiplier. Ignore any overflow.

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

# Remove the rightmost bit from the resultant binary number.

#* Remove the rightmost bit from the resultant binary numbermultiplicand.

<small><nowiki>**</nowiki> Note that an arithmetic shift preserves the sign of a 2's complement number.</small>