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.
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.