Digital Electronics

HACKING MULTIPLICATION WITH KARATSUBA’S ALGORITHM

people tend to obsess over making computer software application faster. You can, of course, just crank up the clock speed as well as add more processors, however frequently the most powerful method to make something quicker is to discover a much better method to do it. sometimes those techniques are extremely different from exactly how a human being would do the exact same task, however it fits the computer’s capabilities. [Nemean] has a video explaining a much better multiplication algorithm understood as Karatsuba’s algorithm as well as it is really rather clever. You can see the video below.

To assist you comprehend the algorithm, the video shows a simple two-digit by two-digit multiplication. You can see that the very first as well as last digits are essentially the result of one multiplication. It is all the intermediate digits that add together. The only thing that may modification the very first digit is a carry.

Using clever math, you can compute the very first as well as last digit, together with a sum that contains the middle parts added to the very first as well as last digits. By subtracting them out, you can get all the needed digits utilizing fewer multiplications than the traditional method. adding as well as subtracting is generally cheap, so trading those for multiplications can result in major time savings.

Of course, these days your multiplication most likely occurs in hardware however it still may not be as quick as addition as well as subtraction. The complexity of this algorithm, though, means it isn’t frequently utilized unless you are dealing with extremely big numbers. Either way, it is a clever application of math as well as disproved what “everyone” understood — that the very best technique had already been found. It makes you question exactly how many other understood things will be disproven in the future.

We are always thinking about strange math methods. a few of them are rather colorful.

Leave a Reply

Your email address will not be published. Required fields are marked *