Since dividing by two (ignoring remainders) is just a left shift, and multiplying by two is just a right shift, this means you can do multiplication with just <<, >>>, and +.
Of course, here's another, er, related algorithm. Take your two numbers A and B. Make a variable called C, initially set to 0. Iteratively decrease A by 1, and increase C by B. Do this until A = 0. Then C is your answer. Everyone knows this technique, it's obvious. But it means that you can do multiplication with just + and --.
I wonder what other ways you can do multiplication with a limited set of mathematical operators.
The other interesting property to the first algorithm is that you don't need to calculate a conditional for each bit in one of those factors. You can just AND each bit in one factor by all the bits in the other factor (ANDing is equivalent to multiplying in binary), before the shifts and the adds. Because ANDs, shifts, and adders are extremely simple to implement in hardware, most (all?) binary multiplication circuits are based off of the peasant multiplication algorithm, with modifications that trade off expense of manufacturing (more gates) for quicker computation (less gate delay due to exploiting parallelism in the algorithm).
Comments
Since dividing by two (ignoring remainders) is just a left shift, and multiplying by two is just a right shift, this means you can do multiplication with just <<, >>>, and +.
Of course, here's another, er, related algorithm. Take your two numbers A and B. Make a variable called C, initially set to 0. Iteratively decrease A by 1, and increase C by B. Do this until A = 0. Then C is your answer. Everyone knows this technique, it's obvious. But it means that you can do multiplication with just + and --.
I wonder what other ways you can do multiplication with a limited set of mathematical operators.
The other interesting property to the first algorithm is that you don't need to calculate a conditional for each bit in one of those factors. You can just AND each bit in one factor by all the bits in the other factor (ANDing is equivalent to multiplying in binary), before the shifts and the adds. Because ANDs, shifts, and adders are extremely simple to implement in hardware, most (all?) binary multiplication circuits are based off of the peasant multiplication algorithm, with modifications that trade off expense of manufacturing (more gates) for quicker computation (less gate delay due to exploiting parallelism in the algorithm).