Thursday, March 01, 2007

A fun way to multiply numbers



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))
Post a Comment