Booth's multiplication algorithm: Difference between revisions

Revision as of 01:50, 9 October 2005

Revision as of 01:51, 9 October 2005

Line 17:

==Example==

We wish to multiplyFind 3 *× -4:

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

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

* Perform the loop four times :

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

** 0000110'''00'''. The last two bits are 00.

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

** 000001100. A right shift.

## 0000 011'''0 0''' (ashift-right performed [1/4])

** 0000011'''00'''. The last two bits are 00.

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

** 000000110. A right shift.

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

** 0000001'''10'''. The last two bits are 10.

## 0000 001'''1 0''' (ashift-right performed [2/4])

** 110100110. Add the negative of the multiplicand.

## 0000 001'''1 0''' (check performed)

** 111010011. A right shift.

## 1101 001'''1 0''' (subtract performed)

** 1110100'''11'''. The last two bits are 11.

## 1110 100'''1 1''' (ashift-right performed [3/4])

** 111101001. A right shift.

## 1110 100'''1 1''' (check performed)

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

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

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

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