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


QUESTION:

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?

[Prev][TOC][Next]


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