Hacking Multiplication with Karatsuba’s Algorithm

People tend to obsess over making computer software faster. You can, of course, just crank up the clock speed and add more processors, but often the most powerful way to make something faster is to find a better way to do it. Sometimes those methods are very different from how a human being would do the same task, but it suits the computer’s capabilities. [Nemean] has a video explaining a better multiplication algorithm known as Karatsuba’s algorithm and it is actually quite clever. You can see the video below.

To help you understand the algorithm, the video shows a simple two-digit by two-digit multiplication. You can see that the first and last digits are essentially the result of one multiplication. It is all the intermediate digits that add together. The only thing that might change the first digit is a carry.

Using clever math, you can compute the first and last digit, along with a sum that contains the middle parts added to the first and last digits. By subtracting them out, you can get all the required digits using fewer multiplications than the traditional method. Adding and subtracting is generally cheap, so trading those for multiplications can result in major time savings.

Of course, these days your multiplication probably occurs in hardware but it still may not be as fast as addition and subtraction. The complexity of this algorithm, though, means it isn’t often used unless you are dealing with very large numbers. Either way, it is a clever application of math and disproved what “everyone” knew — that the best method had already been found. It makes you wonder how many other known things will be disproven in the future.

We are always interested in odd math methods. Some of them are rather colorful.