Binary Multiply - Repeated Shift and Add

Repeated shift and add - starting with a result of 0, shift the second multiplicand to correspond with each 1 in the first multiplicand and add to the result. Shifting each position left is equivalent to multiplying by 2, just as in decimal representation a shift left is equivalent to multiplying by 10.

  1. Set result to 0
  2. Starting from the right
  3. Repeat
  4. Shift 2nd multiplicand left until rightmost digit is lined up with leftmost 1 in first multiplicand
  5. Add to result
  6. Remove that 1 from 1st multiplicand
  7. Until 1st multiplicand is zero
  8. Result is correct


What is the average number of operations needed to complete each of these algorithms under when the two numbers to be multiplied have n digits in their representation?


Last updated 2000/02/07
© J.A.N. Lee, 2000.