Multiplication made easy?
Today on Freakonomics, Steven Levitt describes an alternative way to do multiplication. It’s also explained in this Wikipedia entry. Basically it’s a way of doing multiplication in binary (meaning base 2), even though you start with numbers written in base 10. In other words, you write one number as a sum of powers of 2 (e.g. 13 = 1 + 4 + 8), then multiply each of the powers by the other number (so 19*13 = 19*1 + 19*4 + 19*8). The second step only involves addition and repeated doubling of the other number, so it can be done fairly quickly.
I’m avoiding the temptation to rehash Steven’s more detailed example and Wikipedia’s explanation. Instead, I just wanted to highlight both pages as an illustration of what computer science is all about. Computer scientists don’t sit around and multiply numbers all day, but we also don’t write computer programs all day either. Instead we worry about the best way to solve problems (often problems involving numbers). Early on computer scientists realized that binary representations of numbers made it simpler to design circuits that performed arithmetic. They also asked questions like “How many steps does it take to multiply two number?”
Whether done by a computer, a person, or some sort of trained animal, the algorithm described above takes about the same number of steps as the traditional method we all learned in school. If you have two n digit numbers, the number of steps required is proportional to n*n (here a “step” means multiplying two digits, or adding two digits). The advantage of the nontraditional algorithm is that you don’t need to remember anything from a multiplication table, you just need to know how to know how to add digits and divide by 2.
It turns out that much faster algorithms exist. If you (or your computer) ever need to multiply two very long numbers, the Karatsuba Multiplication Algorithm requires many fewer steps. For small numbers, however, it’s more complicated, so don’t feel bad about not knowing about it.