What is the Karatsuba Multiplication Algorithm?
Exploring a faster way of multiplying two integers than the old grade-school method.
How do you calculate 3 x 4? The obvious answer is that we were made to by-heart tables during our schooling and we know the answer is 12. How about calculating 23 x 42, some of us may multiply it in our minds, while others use a pen and paper, and we come to the result 966. What would you do, if I increased the number of digits from 3,4,… up to say 60 in the multiplier and multiplicand, we would try the multiplication method taught to us, right.
But to our surprise, we need not use the long-old multiplication method. Karatsuba Multiplication Algorithm comes to our rescue here. What is this? How is it implemented? And will this introduce efficiency in the calculation as the number of digits increases? After reading this article, all such questions will be answered, so keep reading.
Table of Contents:
Before diving right into Karatsuba, let’s touch upon algorithms. As we all know, algorithms comprise a series of steps/instructions, devised to solve a computational problem. These computational problems range from simple integer multiplication to XYZ. (P.S. I was amazed when I read about this integer multiplication application.) The importance of using such algorithms becomes highly evident when the input size is large enough (tending to infinity). Not that humans or modern computer calculators cannot solve them, but we need not worry about accuracy and precision when solving computational problems using algorithms. Adding a beautiful mantra by Alfred V. Aho that says-
“Perhaps the most important principle for the good algorithm designer is to refuse to be content.”
So, as an algorithmic programmers, we should always think, can we do better? As in the case of the integer multiplication, indeed Karatsuba algorithm is better than the old-school method.
Without further adieu, let’s jump to the steps involved in the Karatsuba Multiplication Algorithm.
Problem Statement: Consider multiplying two numbers, with their maximum length being n.
Get Rishika Gupta’s stories in your inbox
Join Medium for free to get updates from this writer.
Steps:
1. Rewrite x and y in the form of n/2 digits in the form of a, b, c, and d.
2. Compute the value of ac.
3. Compute the value of bd.
4. Compute the value of (a+b)(c+d)
5. Calculate ad + bc by subtracting the answer of step4 — step3 — step2
6. Finally compute the answer by making a few additions/subtractions to our computed values using the below expression.
It is important to note that we are calculating ad + bc, by multiplying (a+b) and (c+d) and then performing some subtractions. This is crucial for algorithmic performance, as we know that additions/subtraction operations are faster than multiplications. By doing so, we are making 3 recursive multiplications instead of 4, saving us big-time.
For instance, consider x = 5678 and y = 1234.
Let me also prove why this method works to multiply two integers.
Proof:
Moving ahead with the Algorithm Implementation in Python Language:
You can view the entire code on GitHub here.
The runtime complexity of the algorithm:
To analyze the complexity of the Karatsuba algorithm, consider the number of multiplications the algorithm performs as a function of n, M(n). As we discussed earlier, the algorithm makes 3 recursive calls. If n = 2^k for any value of k, then the algorithm recurses thrice on n/2 digit numbers, thus ending up with a recurrence relation:
Apart from the recursive multiplications, the additions and subtractions involved throughout the procedure will be taken care of in O(n). Thus, the overall time complexity is:
Applying the Master’s Theorem for the above recurrence equation, we derive the running time as:
which is faster than O(n²). (n-digit * n-digit multiplication).
Hope this article was helpful to you. Thanks for reading! Do subscribe and share with everyone in your community and don’t forget to like and comment. Follow my Medium Page Rishika Gupta.
More content at PlainEnglish.io. Sign up for our free weekly newsletter. Follow us on Twitter and LinkedIn. Check out our Community Discord and join our Talent Collective.
