Binary Multiply

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?