Multiplication

Paper and pencil example:

Multiplicand    1000
Multiplier    x 1001
                1000
               0000
              0000
             1000   
Product      1001000

Multiply Hardware Version 1

Multiply Algorithm Version 1

Observations on Multiply Version 1

Multiply Hardware Version 2

Multiply Algorithm Version 2

Observations on Multiply Version 2

Multiply Hardware Version 3

Multiply Algorithm Version 3

Observations on Multiply Version 3

What about signed multiplication?

Easiest solution is to make both positive & remember whether to
complement product when done (leave out the sign bit, run for 31 steps)

Booth's Algorithm is more elegant way to multiply signed numbers using same hardware as before
Motivation for Booth's Algorithm

Example 2 x 6 = 0010 x 0110:

             0010
           x 0110
           + 0000 shift (0 in multiplier)
          + 0010  add   (1 in multiplier)
         + 0010   add   (1 in multiplier)
        + 0000    shift (0 in multiplier)
         00001100

Replace a string of 1s in multiplier with an initial subtract when we first see a one and then later add for the bit after the last one. For example

            0010
          x 0110
          + 0000 shift (0 in multiplier)
         - 0010  sub   (first 1 in multiplier)
        + 0000   shift (middle of string of 1s)
       + 0010    add   (prior step had last 1)
        0001100

Booth's Algorithm Insight
Current Bit Bit to the Right Explanation Example
1 0 Beginning of a run of 1s 0001111000
1 1 Middle of a run of 1s 0001111000
0 1 End of a run of 1s 0001111000
0 0 Middle of a run of 0s 0001111000
Originally for Speed since shift faster than add for his machine

Booth's Algorithm

1. Depending on the current and previous bits, do one of the following: 2. As in the previous algorithm, shift the Product register right (arithmetic) 1 bit.

Example: 2 x 6
m=2,p=6;

  m = 0010
  p = 0000 0110 

     p
0000 0110 0 no-op
0000 0011 0 >> p
1110 0011 0 p = p - m
1111 0001 1 >> p
1111 0001 1 no-op
1111 1000 1 >> p
0001 1000 1 p = p + m
0000 1100 0 >> p

=12
 
Example: 2 x -3

   m = 0010
   p = 0000 1101 

1110 1101 0 p = p - m
1111 0110 1 >> p
0001 0110 1 p = p + m
0000 1011 1 >> p
1110 1011 0 p = p - m
1111 0101 1 >>p
1111 0101 1 no-op
1111 1010 1 >>p

=-6