Back to ComputerTerms

= Booth's Algorithm for Multiplication =

{{{
   1. Set product = Multiplier
   2. Depending on the current and previous bits, do one of the following:

      00: Middle of a string of 0's, so no arithmetic operation.
      01: End of a string of 1's so add the multiplicand to the left half of the product
      10: Beginning of a string of 1s, so subtract the multiplicand from the left half of the product.
      11: Middle of a string of 1's, so no arithmetic operation.

   3. Shift the product register right 1 bit (1 if 1 and 0 if 0) and go to 2.


Example:


0010        Multiplicand negative = 1110 (-2)
1101 x      Multiplier
-----------
1111 1010

Product:
           Prev
0000 1101 (0)   -2    --> 
1110 1101 (1)   Shift --> 
1111 0110 (1)   +2    -->
0001 0110 (1)   Shift --> 
0000 1011 (0)   -2    -->
1110 1011 (0)   Shift --> 
1111 0101 (1)   Shift -->
1111 1010 (1)   Answer 

}}}

Back to ComputerTerms