Reading through the algorithms book by Papadimitriou, et. al has been great fun. I learn a great fun way to multiply (apparently known from ancient times). Let's say we intend to multiply 13 and 23, the procedure is quite straight forward. Write down 13 and 23 besides each other
| 13 | 23 |
| 6 | 46 |
| 3 | 92 |
| 1 | 184 |
The first column is divided by two (with rounding) and the second one is multiplied by two
| 13 | 23 |
| 6 | 46 |
| 3 | 92 |
| 1 | 184 |
Strike out the numbers with even numbers in the first column
Now we just add up the numbers in the right column to obtain 299. That's quite easy right? The really cool thing about this approach is that is easy to implement using computers (hint: left shift and right shift multiply and divide the number by 2 (with rounding taken care of))
2 comments:
This is in fact the way multiplication is implemented within the ALU at the circuit level.
If you know the bit vector size, you can create a single circuit (without having to worry about a loop with arbitrary number of iterations since a 8 bit number will have this operation repeated only 8 times).
Thanks for pointing that out. Yes, I can see how such multiplication can be easy to implement in hardware.
Do you have any other references - hardware, that I can add to this blog entry?
Thanks,
Balbir
Post a Comment