Booths :
 
    Note that  99909 * 51 can be restated as (100000 - 100 + 10 - 1) * 51
      100000 - 100 = 99900  99900 + 10 = 99910  99910 - 1 = 99909

      (100000 - 100 + 10 -1) * 51

      Pad 51 with zeros and add or subtract.
      5100000 - 5100 + 510 - 51 = 5094849

  Same works with binary :  
    Since the only value a position can hold is 0 or 1, this will work
      with all values.

    Assume a virtual bit to the right of the least significant bit of 
      multiplier.
      Set virtual bit to zero.
      Set product (accumulator) to zero.

    Start at the 1st real bit of multiplier

    While multiplier > 0  (at least one 1 bit set) 
      If least significant bit (lsb) is 1 and virtual bit to the right is zero,
        subtract multiplicand from product.

      Else if lsb is 0 and virtual bit is 1, 
        add multiplicand to product.

      Else if bits same,  
        Don't do anything with it.

      Logical shift multiplicand left (right pad with zero), 
      Shift multiplier right into virtual bit (left pad with zero).

    Done


  23 * 14 

00010111b * 00001110b

                            virtual 
Multiplier  0 0 0 0 1 1 1 0   0 
                   +     -  
             virtual            applied
              bit                 value      product
       10111       Multiplicand
        1110   0   Multiplier
                   no action          0             0

      101110       Mulitiplicand 
         111   0   Multiplier
                   subtract      -10110        -10110

     1011100       Multiplicand
          11   1   Multiplier
                   no action     -10110        -10110

    10111000       Multiplicand
           1   1   Multiplier
                   no action     -10110        -10110

   101110000   1   Multiplicand
           0   1   Multiplier
                   add       +101110000    1011000010    

  1011100000   
           0   0   shift, accumulate look can break here
               ...

  1011110000
 -    101110
 -----------
  1011000010

Our example               4 shifts and 2 adds and 4 loop tests.
                            (shifts of both values done in parallel)

For 8 bit number          Best case   1 shift, one add, 2 tests.
                          Worst case  8 shifts, 8 adds, 9 tests.

  Testing multiplier for 0 can break loop early. 


Another Booth's example

This variation is more CPU hardware friendly. It also has an additional
  virtual bit on the left to handle the most negative 4 bit value, if used.

2 4-bit signed numbers, m = 3 (0011) and r = -4 (1100)

Work register A, S, and P  9-bits each.

Fill A with a copy of m, fill from most significant bit and pad with zeros..
Fill S with the 2s complement of m (1101) from most significant bit and pad with
  zeros.
Fill P with zeros in the most significant bits followed by r followed by a 0
  in the least significant bit.

m 0011 !m 1101 r 1100

A 0 0011 0000
S 1 1101 0000
P 0 0000 1100 0 
          - -
Note bit to left required to handle most negative values and takes on
the sign of the current product.

If the last two bits of P are 0 1 then add A to P.
If the last two bits of P are 1 0 then add S to P. (or subtract A from P)
If the last two bits of P are 0 0 or 1 1 then skip math.
Arithmetically shift P to the right (divide by 2).
  Note arithmetic shift preserves the current sign of P.

P 0 0000 1100 0  Initial product
1st test    0 0
P 0 0000 0110 0  arithmetic shift only

2nd test    0 0
P 0 0000 0011 0  arithmetic shift only

3rd test    1 0  subtract (add S) 
S 1 1101 0000  
P 1 1101 0011 0  P=P+S  (or subtract A)
P 1 1110 1001 1  arithmetic shift 

4th test    1 1
P 1 1111 0100 1  arithmetic shift 
    ---- ----  
   remember the two 'virtual' bits are only there for computation.

To check, convert result to its positive value :
          1111 0100
  flip    0000 1011
  add 1   0000 1100  (12)



If working with most negative value is required, an additional bit on the left
of the A and S work registers is required.

  Example 4-bit values  -8 = 1000

  A 1 1000 0000  -8
  S 0 1000 0000  +8
    Because it is now a 5-bit number, the sign bit is not extended.
       1 1000 0000 -8
       0 0111 1111 flip
     +           1 add 1
       0 1000 0000 +8


  -8 (1000) * -5 (1011)

     P   0 0000 1011 0
                   - -
     S   0 1000 0000 0
         0 1000 1011 0  P + S
         0 0100 0101 1  ASL 1
                   - -

 shift-2 0 0010 0010 1  ASL only 2
                   - -

     A   1 1000 0000 1
         1 1010 0010 1  P + A
         1 1101 0001 0  ASL 3
                   - -

     S   0 1000 0000 0
         0 0101 0001 0  P + S
         0 0010 1000 1  ASL 4
           ---- ----

             32 + 8  = 40 (-8*-5)

Booths requires the working multiplicand, multiplier, and product registers
to be twice the size of the numbers + 1 bit.

Booth uses arithmetic shifts (properly keeps the sign during the shift.).

Booths more commonly implemented in software on real (float) values rather
  than integers in hardware.

Booths works with signed values.

Other algorithms available - Baugh-Wooley, Wallace tree, Dadda tree, Peasant. 
 * Many of these are variations on shift and add.

When designing hardware, both speed and number of gates (complexity) are taken 
into account.

More advanced CPUs may choose between algorithms.

Certain algorithms work better with signed values than others.