Booth's Multiplication Algorithm - Example

Example

Find 3 × (−4), with m = 3 and r = −4, and x = 4 and y = 4:

  • m = 0011, -m = 1101, r = 1100
  • A = 0011 0000 0
  • S = 1101 0000 0
  • P = 0000 1100 0
  • Perform the loop four times :
    1. P = 0000 1100 0. The last two bits are 00.
      • P = 0000 0110 0. Arithmetic right shift.
    2. P = 0000 0110 0. The last two bits are 00.
      • P = 0000 0011 0. Arithmetic right shift.
    3. P = 0000 0011 0. The last two bits are 10.
      • P = 1101 0011 0. P = P + S.
      • P = 1110 1001 1. Arithmetic right shift.
    4. P = 1110 1001 1. The last two bits are 11.
      • P = 1111 0100 1. Arithmetic right shift.
  • The product is 1111 0100, which is −12.

The above mentioned technique is inadequate when the multiplicand is the largest negative number that can be represented (e.g. if the multiplicand has 4 bits then this value is −8). One possible correction to this problem is to add one more bit to the left of A, S and P. Below, we demonstrate the improved technique by multiplying −8 by 2 using 4 bits for the multiplicand and the multiplier:

  • A = 1 1000 0000 0
  • S = 0 1000 0000 0
  • P = 0 0000 0010 0
  • Perform the loop four times :
    1. P = 0 0000 0010 0. The last two bits are 00.
      • P = 0 0000 0001 0. Right shift.
    2. P = 0 0000 0001 0. The last two bits are 10.
      • P = 0 1000 0001 0. P = P + S.
      • P = 0 0100 0000 1. Right shift.
    3. P = 0 0100 0000 1. The last two bits are 01.
      • P = 1 1100 0000 1. P = P + A.
      • P = 1 1110 0000 0. Right shift.
    4. P = 1 1110 0000 0. The last two bits are 00.
      • P = 1 1111 0000 0. Right shift.
  • The product is 11110000 (after discarding the first and the last bit) which is −16.

Read more about this topic:  Booth's Multiplication Algorithm

Famous quotes containing the word example:

    “Our intellect is not the most subtle, the most powerful, the most appropriate, instrument for revealing the truth. It is life that, little by little, example by example, permits us to see that what is most important to our heart, or to our mind, is learned not by reasoning but through other agencies. Then it is that the intellect, observing their superiority, abdicates its control to them upon reasoned grounds and agrees to become their collaborator and lackey.”
    —Marcel Proust (1871–1922)