Booth's multiplication algorithm: Difference between revisions

Revision as of 01:33, 9 October 2005

Revision as of 01:42, 9 October 2005

Line 6:

* Add a 0 to the right of the multiplier.

*Repeat theseCount twohow stepsmany forbits each bitare in the multiplier. That many times, do this :

*# If the two rightmost bits are...

*#* 00 or 11: do nothing.

*#* 01: add the multiplicand to the left half of the multiplier. Ignore any overflow.

*#* 10: add the negative of the multiplicand to the left half of the multiplier. Ignore any overflow.

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

* Remove the rightmost bit from the multiplicand.

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

==Example==

We wish to multiply 3 * -4:

* The multiplicand, 3, is 0011; its negative is 1101.

# Multiplier (-4): 1100

* The multiplier, -4, is 1100; with all zeroes added, it is 000011000.

# Multiplicand (3): 0011

# Add 0s to the left of the multiplier (1100) in a quantity equivalent to the number of bits in the multiplicand (4 bits): 0000 1100

# Add a 0 to the right of the binary number that results from the previous step: 0000 1100 0

# Rightmost bit check loop:

## 0000 110'''0 0''' (check performed)

## 0000 110'''0 0''' (did nothing)

Line 37 ⟶ 33:

## 1110 100'''1 1''' (did nothing)

## 1111 010'''0 1''' (ashift-right performed [4/4])

# Remove the rightmost bit from the resultant binary number: 1111 0100

* The result is 11110100<s>0</s>, which is -12.

1111 0100 in two's complement = -(00001011+1) = -(00001100) = -12

==Why does Booth's Algorithm work ?==