Karatsuba Algorithm for Multiplying Two Integers
A divide and conquer approach for multiplication
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
