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.

  • Set result to 0
  • Repeat
    • Shift 2nd multiplicand left until rightmost digit is lined up with leftmost 1 in first multiplicand
    • Add 2nd multiplicand in that position to result
    • Remove that 1 from 1st multiplicand
  • Until 1st multiplicand is zero
  • Result is correct
  • STOP

Consider the following problem in multiplication:

Click on the image to cycle through the multiplication steps.


QUESTION:

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

[Prev][TOC][Next]


Last updated 2001/10/08
© J.A.N. Lee, 2000-2001.