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.

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?
Last updated 2000/02/07
© J.A.N. Lee, 2000.