Karatsuba Algorithm for Multiplying Two Integers
All of us learned how to multiply two numbers when we were kids. In case we have forgotten (😄), let’s look at how to multiply two numbers 19 and 95.
Multiplying 19 and 95 requires 4 (2²) elementary operations as shown above. Similarly multiplying 123 and 456 would require 9 (3²) elementary operations. Thus, if we generalize, given two n-digit numbers, this traditional approach requires n² elementary multiplication operations. Therefore, the time complexity of this naive approach is O(n²).
Is this the only possible way to multiply two numbers? 🤔
In 1960, a Russian mathematician named Anatoly Alexeyevich Karatsuba discovered a new algorithm for multiplying two numbers. Let us look at how this algorithm works.
The Karatsuba Algorithm
Let’s consider two 4-digit numbers x and y where x=1234 and y=5678. First of all, we should divide the n-digit numbers into n/2-digit numbers as shown below.
a and c represent the first n/2 digits of x and y. Similarly, b and d represent the last n/2 digits of x and y
The Karatsuba algorithm involves 4 main steps.
Finally, multiply the output of step 1 by 10ⁿ, the output of step 4 by 10^(n/2), and add them both with the output of step 2 (as shown below).
If you multiply 1234 and 5678, the answer would be 7006652. Seems pretty easy right!!!
But, how does this work? 🤔
Let us break this down. As abovementioned, let x = 1234 and y = 5678. We also have defined a = 12, b = 34, c = 56 and d = 78.
If we write x and y in terms of a, b, c and d:
Now, if we multiply x and y:
We have computed ac in step 1 and bd in step 2. In step 3, we computed (a+b).(c+d) = ac + ad + bc + bd. In order to get (ad + bc), we should subtract ac and bd. That is what we are doing in step 4. If we summarize,
Now, all the 4 steps that we did earlier make sense.
Python Implementation of Karatsuba Algorithm
This implementation utilizes recursion. Steps 1, 2, and 3 are performed in lines 21, 22, and 23. Finally, the output of step 4 is returned in line 25. The recursive calls should have a termination condition. Here, when the values of a, b, c, and d become single digits (0–9), recursion terminates (lines 8 and 9).
One interesting question to ask at this point would be:
We need to calculate ac, ad, bc, and bd. ac and bd are calculated in steps 1 and 2. We could have calculated ad and bc in two additional steps as well. But instead, we multiply (a+b).(c+d) and then subtract ac and bd. Why? 🤔
The reason is to reduce the number of recursive calls. The current implementation only requires three recursive calls. If we calculate ad and bc separately, the number of recursive would become 4. Keeping the number of recursive calls at a minimum would provide better performance.
How is Karatsuba Algorithm Better than the Traditional Approach?
Earlier, we saw that the traditional approach has the complexity of O(n²). Now, let us try to figure out the time complexity of the Karatsuba algorithm.
Given 2 n-digit numbers, the algorithm recurses three times on n/2-digit numbers. Hence, the complexity can be expressed as:
If we solve this, the time complexity would be:
log₂³ is approximately equal to 1.585 < 2. Therefore, for sufficiently large n, the Karatsuba algorithm will perform better (less running time) compared to the traditional naive approach.
Hope you enjoyed the article !!!