Home | Projects | Notes > Computer Architecture & Organization > Multiplication & Division

Multiplication & Division

Shifting Operation

• Shifting in general means moving the bits stored in a register one or more positions to the right or left.

• Arithmetic shift

  • Arithmetic Shift Left (Multiplication)

    • Each bit is shifted towards left, MSB is discarded and LSB becomes 0. (Similar to logical shift)

      • In this example, the operation has overflowed. Meaning, the result of the multiplication is larger than the largest possible value.

  • Arithmetic Shift Right (Division)

    • Each bit is shifted towards right, LSB is discarded and MSB is preserved.

Unsigned Binary Multiplication - Partial Products

• Humans do all the multiplication first, then add up those numbers to get the final product.

  • Human's multiplication example:

    xxxxxxxxxx
    9
    1
       0010  Multiplicand (2 in base-10)
    2
     x 0011  Multiplier (3 in base-10)
    3
     ------ 
    4
       0010  Partial product
    5
      0010   Partial product
    6
     0000    Partial product
    7
    0000     Partial product
    8
    -------
    9
    0000110  Final result
    

• Computers do it a little differently by using the Paritial Product Algorithm.

  • Here, the multiplication of two $n$$n$-bit numbers needs to have a $2n$$2n$ bits to store the result.

    • ∵ The result can be as big as $2n$$2n$ bits. (Make sure that your partial product register has enough room to store the information.)

  • Computer's partial product algorithm for multiplication:

    xxxxxxxxxx
    8
    1
    Step a.   Set a counter to n.
    2
    Step b.   Clear the 2n-bit partial product register.
    3
    Step c.   If the right most bit of the multiplier is one, add the multiplicand to the 
    4
              n most-sificant bits of the partial product.
    5
    Step d.   Shift the partial product one place to the right.
    6
    Step e.   Shift the multiplier one place to the right (the rightmost bit is lost.)
    7
    Step f.   Decrement the counter and repeat from step c until the count is 0 after n cycles. 
    8
              The product is in the partial product register.
    

  • Example:

    xxxxxxxxxx
    21
    1
    Multiplicand = 0010 (2 in base-10)
    2
    Multiplier = 0011 (3 in base-10)
    3
    +-------------------------------------------------------------+
    4
    | Cycle |   Step    | Counter |  Multiplier | Partial Product | 
    5
    +-------------------------------------------------------------+
    6
    |       |   a, b    |    4    |    0011     |    0000 0000    |
    7
    | 1     |   c       |    4    |    0011     |    0010 0000    |
    8
    | 1     |   d, e    |    4    |    0001     |    0001 0000    |
    9
    | 1     |   f       |    3    |    0001     |    0001 0000    |
    10
    +-------------------------------------------------------------+
    11
    | 2     |   c       |    3    |    0001     |    0011 0000    |
    12
    | 2     |   d, e    |    3    |    0000     |    0001 1000    |
    13
    | 2     |   f       |    2    |    0000     |    0001 1000    |
    14
    +-------------------------------------------------------------+
    15
    | 3     |   c       |    2    |    0000     |    0001 1000    |
    16
    | 3     |   d, e    |    2    |    0000     |    0000 1100    |
    17
    | 3     |   f       |    1    |    0000     |    0000 1100    |
    18
    +-------------------------------------------------------------+
    19
    | 4     |   c       |    1    |    0000     |    0000 1100    |
    20
    | 4     |   d, e    |    1    |    0000     |    0000 0110    | Final result
    21
    +-------------------------------------------------------------+
    

    With negative number this complicates the algorithm. Skip negative number multiplication and Booth's Algorithm.

High Speed Multiplication

• Practical computers accelerate multiplication in various ways as multiplication by shifting and adding is relatively slow.

  • Partial Product Algorithm can cause many iterations which can drastically decrease the speed of the operation as the register size gets bigger.

• Faster multiplications:

  • Use shift and add in a different way.

    • Can only be used when you know the multiplier at coding.

      xxxxxxxxxx
      6
      1
      x10 can be done by,
      2
      
      3
      1. Shift left             (original value x 2)
      4
      2. Shift left             (now becomes, original value x 4)
      5
      3. Add original value     (now becomes, original value x 5)
      6
      4. Shift left             (now becomes, original value x 10)
      

  • Use a look-up table like an array.

    • Can be used when you do NOT know the numbers at coding.

    • Define the table in memory (ROM) and use the input numbers to look up the result. (It is fast because only one memory reference is required.)

    • Trading memory for speed!

      • Faster than the Partial Product Algorithm but memory to store this table is required.

      • No need to store the whole 256 bytes shown in the following example. Only 120 bytes need to be stored. Think!

• Using smaller look-up tables with larger operands.

  • Split the binary number in half and do the mutiplication so that it can be carried out only by using smaller look-up tables.

  • Example: Multiplication of two 16-bit binary numbers

    xxxxxxxxxx
    13
    1
    A = A(upper)*256 + A(lower)           or A1*256 + A0 
    2
    B = B(upper)*256 + B(lower)           or B1*256 + B0 
    3
    
    4
    A * B = (A1*256 + A0)(B1*256 + B0)
    5
          = 65536*A1*B1 + 256*A1*B0 + 256*A0*B1 + A0*B0
    6
    
    7
    Since multplying by 2 can easily be done with shifting,
    8
    65536 = 2^16 (16 left shifts)
    9
    256   = 2^8 (8 left shifts)
    10
    
    11
    The split parts' range would be 00 to FF(255). 
    12
    The array size would be 256*256 = 65536 with each element being 32 bits.
    13
    (This array can be further downsized due to its symmetricity, etc.)
    

  • This technique can be used for any number of bits.

    • If you use a smaller table (i.e., 16 x 16) and larger numbers (i.e., 32-bits) then the numbers have to e broken into 4-bits each.

      xxxxxxxxxx
      3
      1
      A = A7A6A5A4A3A2A1A0
      2
      
      3
      A = (2^28 * A7) + (2^24 * A6) + ... + (2^8 * A2) + (2^4 * A1) + A0
      

    • Smaller table, but more look-ups, partial products to keep track of and shifts.

Division

• Division can be performed by repeated subtraction.

  • The loop stops when the result is less than the divisor.

  • The ARM does not have a division instruction at the assembly level. You have to write that yourself.

    • Division is not supported by the CPU (32-bit architecture) we are using for this course, but might be supported in the future generation CPUs.

    • The easiest algorithm is just do repeated subtraction until you get 0 or a negative number for a remainder.

  • Example:

    xxxxxxxxxx
    9
    1
    Dividend - Divisor    Quotient    Remainder
    2
    ------------------    --------    ---------
    3
    20                    0           0
    4
    20-3 = 17             1           17
    5
    17-3 = 14             2           14
    6
    14-3 = 11             3           11
    7
    11-3 =  8             4           8
    8
     8-3 =  5             5           5
    9
     5-3 =  2             6           2         <----- Stop here!
    

    This algorithm can get really slow when dividing a large number by a small number.

  • Hardware can be used to implement the better division algorithms.

Restoring Division

• Restoring division is basically the traditional pencil and paper algorithm we use to perform division. The only difference is that we, as humans, compare the divisor with the partial dividend mentally whereas computers must perform a subtraction and test the sign of the result.

  • If result > 0, a 1 is shifted into a quotient.

  • Else, a 0 is shifted into a quotient and the divisor is added back to the partial dividend to restore it to its previous value.

• Restoring Division Algorithm

  1. Align the divisor with the MSB of the dividend.

  2. Subtract the divisor from the partial dividend.

  3. If the resulting partial dividend is negative, place a 0 in the quotient and add back the divisor to restore the partial dividend.

  4. If the resulting partial dividend is positive, place a 1 in the quotient.

  5. Perform a test to determine end of division. If the divisor is aligned so that its LSB corresponds to the LSB of the partial dividend, stop. The final partial product is the remainder. Otherwise, continue with step 6.

  6. Shift the divisor one place right. Repeat from step 2.

• Example: Dividing 01100111(2) by 1001(2)

  xxxxxxxxxx
  19
  1
  Step Description                           Partial Dividend Divisor  Quotient
  2
  ---- ------------------------------------- ---------------- -------- --------
  3
       (Initial)                                     01100111 00001001 00000000
  4
  1    Align                                         01100111 01001000 00000000
  5
  2    Subtract divisor from partial diviend         00011111 01001000 00000000
  6
  4    Result positive, shift 1 in quotient          00011111 01001000 00000001
  7
  5    Test for end
  8
  6    Shift divisor one place right                 00011111 00100100 00000001
  9
  2    Subtract divisor from partial diviend        -00000101 00100100 00000001 
  10
  3    Restore divisor, shift 0 in quotient          00011111 00100100 00000010
  11
  5    Test for end
  12
  6    Shift divisor one place right                 00011111 00010010 00000010
  13
  2    Subtract divisor from partial diviend         00001101 00010010 00000010
  14
  4    Result positive, shift 1 in quotient          00001101 00010010 00000101
  15
  5    Test for end
  16
  6    Shift divisor one place right                 00001101 00001001 00000101
  17
  2    Subtract divisor from partial diviend         00000100 00001001 00000101
  18
  4    Result positive, shift 1 in quotient          00000100 00001001 00001011
  19
  5    Test for end