Karatsuba Algorithm for fast multiplication of large decimal numbers represented as strings

Approach

We try to use the divide and conquer strategy (if this is new for you, refer here for more information). 

Initially, we try to divide our problem into smaller subproblems as shown below:

1. A * B
2. (A_l * 10^n/2 + A_r) * (B_l * 10^n/2 + B_r)
3. A_l * B_l * 10ⁿ + A_l * B_r * 10^n/2 + A_r * B_l * 10^n/2 + A_r * B_r

We pad our A and B with 0’s in the front to make them have equal and even lengths. We then divide each number into two equal parts (A_l and A_r are equal-sized parts). This way, we have split our original multiplication into 4 different ones with half the original digit size as shown above in step(3).

We can observe the new recurrence, T(N) = 4*T(N/2) + O(N), the O(N) is there because addition and subtraction take O(N) time for N digit numbers. Solving the above recurrence using the Master’s Theorem (read about Master’s Theorem here), we get O(N²). 

There isn’t any improvement from our school grade algorithm through the above divide and conquer approach to the problem. 

So, to obtain a better time complexity than O(N²) we’ll try to change the above equation using a bit of algebra in the following way:

1. A_l * B_l * 10ⁿ + A_l * B_r * 10^n/2 + A_r * B_l * 10^n/2 + A_r * B_r
2. A_l * B_l * 10ⁿ + ((A_l + A_r) * (B_l + B_r) - (A_l * B_l )- (A_r * B_r)) * 10^n/2 + A_r * B_r
3. E_1 * 10ⁿ + (E_2 - E_1 - E_3) * 10^n/2 + E_3, where E_1 = (A_l * B_l), E_2 = ((A_l + A_r) * (B_l + B_r)) and E_3 = (A_r * B_r)

After some algebraic manipulation, we obtain equation (2) from equation (1) by only three unique multiplications which are E_1, E_2 and E_3 respectively.

The other operations such as additions, subtractions or multiplying by 10ⁿ or 10^n/2 take O(N) time.

Hence we obtain a new recurrence, T(N) = 3 * T(N/2) + O(N). Solving this yields O(N^log2(3)), which is approximately equal to O(N^1.59), and this is much better than our school grade algorithm.

The code follows the following steps to implement the above idea.

1. Make essential functions for adding, subtracting, multiplying by a single digit and removing zeros from the front. These functions can be easily implemented and take O(N) time.
2. After having these basics, we need to ensure that we pad our input in the beginning with '0's. This is done to ensure that we have equal-sized inputs with even lengths.
3. Using the essential functions we made earlier, we break the problem into smaller chunks as per equation (2) and return the answer after removing any padded '0's from its front.

Code in C++

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
string remove_zeros_from_front(string a){
   for(int i = 0; i < a.size(); i++){
       // if the digit isn't '0' then all of the numbers after it are returned
       if(a[i] != '0')
           return a.substr(i, a.size() - i);
   }
   // if all the digits were '0' or empty we return "0"
   return "0";
}
string str_add(string a, string b){
   if(a.size() > b.size()) swap(a, b);
   
   int n = a.size();
   int diff = b.size() - a.size();
   string ans;
   int carry = 0;
   for(int i = n-1; i > -1; i--){
       // calculate sum of digits and carry
       int sum_d = (a[i] - '0') + (b[i + diff] - '0') + carry;
       carry = sum_d / 10;
       ans.push_back(sum_d % 10 + '0');
   }
   for(int i = diff - 1; i > -1; i--){
       // calculate sum of extra digits and carry
       int sum_d = (b[i] - '0') + carry;
       carry = sum_d / 10;
       ans.push_back(sum_d % 10 + '0');
   }
   // if there is still a carry then put carry in the answer
   if(carry){
       ans.push_back(carry + '0');
   }
   //reverse to get the answer in the correct order and return
   reverse(ans.begin(), ans.end());
   return ans;
}
string str_sub(string b, string a){
   if(a.size() > b.size()) swap(a, b);
   
   int n = a.size();
   int diff = b.size() - a.size();
   string ans;
   int carry = 0;
   for(int i = n-1; i > -1; i--){
       // subtract digits and carry
       int diff_d = (b[i + diff] - '0') - (a[i] - '0') - carry;
       // if digit difference was negative, set carry to 1
       carry = (diff_d < 0);
       // if digit difference is negative then add 10 to make it non-negative
       diff_d += 10 * carry;
       ans.push_back(diff_d + '0');
   }
   for(int i = diff - 1; i > -1; i--){
       // calculate difffernce of extra digits and carry
       int diff_d = (b[i] - '0') - carry;
       carry = (diff_d < 0);
       diff_d += 10 * carry;
       ans.push_back(diff_d + '0');
   }
   // b > a is the assumption
   assert(carry == 0);
   //reverse to get the answer in the correct order and return
   reverse(ans.begin(), ans.end());
   return ans;
}
string single_dig_mul(string b, char a){
   string ans;
   int d = a - '0', carry = 0;
   for(int i = b.size() - 1; i > -1; i--){
       // multiply all digits with the signle digit d
       int mul_d = (b[i] - '0') * d + carry;
       carry = mul_d / 10;
       ans.push_back(mul_d % 10 + '0');
   }
   // if carry still there then add that to the answer
   if(carry) ans.push_back(carry + '0');
   //reverse to get the answer in the correct order and return
   reverse(ans.begin(), ans.end());
   return ans;
}
string karatsuba(string a, string b){
   // ensure that a is less than equal to b in size
   if(a.size() > b.size()) swap(a, b);
   
   //a is smaller than equal to b
   int A = a.size(), B = b.size();
   if(A == 1) return single_dig_mul(b, a[0]);
   
   string copy_A, copy_B;
   if(B&1){
       // making B have even length by adding '0' in the front
       copy_B.push_back('0');
       B += 1;
   }
   for(int i = 0; i < B - A; i++){
       // adding '0' in front of string a to make both the strings have equal length
       copy_A.push_back('0');
   }
   // both the string copy_A and copy_B are of the same size
   copy_A = copy_A + a;
   copy_B = copy_B + b;
   
   // split string copy_A and copy_B into equal parts, namely
   // A_l and A_r for A and
   // B_l and B_r for B
   string A_l, A_r, B_l, B_r;
   A_l = copy_A.substr(0, B/2);
   A_r = copy_A.substr(B/2, B/2);
   B_l = copy_B.substr(0, B/2);
   B_r = copy_B.substr(B/2, B/2);
   
   /*
   => A * B
   => (Al * 10^(n/2) + Ar) * (Bl * 10^(n/2) + Br)
   => (Al*Bl*10^(n) + (Al*Br + Ar*Bl) * 10^(n/2) + Ar*Br)
   => (Al*Bl*10^(n) + ((Al+Ar)*(Bl+Br)-Al*Bl-Ar*Br)*10^(n/2) + Ar*Br)
   */
   
   // Al * Bl
   string I_1 = karatsuba(A_l, B_l);
   // Ar * Br
   string I_2 = karatsuba(A_r, B_r);
   // (Al + Ar) * (Bl + Br)
   string I_3 = karatsuba(str_add(A_l, A_r), str_add(B_l, B_r));
   // Al * Bl + Ar * Br
   string sum_I1_I2 = str_add(I_1, I_2);
   // (Al + Ar) * (Bl + Br) - (Al * Bl + Ar * Br)
   // (Al + Ar) * (Bl + Br) - Al * Bl - Ar * Br
   I_3 = str_sub(I_3, sum_I1_I2);
   // Al * Bl * 10^(n)
   I_1 += string(B, '0');
   // ((Al + Ar) * (Bl + Br) - Al * Bl - Ar * Br) * 10^(n/2)
   I_3 += string(B/2, '0');
   // (Al*Bl*10^(n) + ((Al+Ar)*(Bl+Br)-Al*Bl-Ar*Br)*10^(n/2) + Ar*Br)
   string I_4 = str_add(I_3, str_add(I_1, I_2));
   
   // remove extra zeros from the front and return result
   return remove_zeros_from_front(I_4);
}
int32_t main(){
   // change input to any number by changing string 'a' and 'b' here
   string a = "907843";
   string b = "578934";
   string ans = karatsuba(a, b);
   cout << ans << endl;
}

Output

525581179362

Time Complexity

The time complexity of the above algorithm can be found using the master’s theorem

O(N^1.59) since the recurrence relation as explained above is T(N) = 3 * T(N/2) + O(N).

Space Complexity

The space complexity for this algorithm is O(N). This is because the memory consumed at any point of the program's execution can be written as N + N/2 + N/2² + N/2³ +.....+ N/2^d (< 2*N).

Also check out - Substr C++

Frequently Asked Questions

1. What are some of the famous Divide and Conquer Algorithms?

Including Karatsuba Algorithm, we have Merge Sort, Quick Sort, Binary Search and Strassens's Algorithm being some of the famous ones with a wide range of applications.

2. What are the uses of the Karatsuba Algorithm?

The Karatsuba Algorithm is a simple algorithm that can easily improve over the school grade algorithm. It has thus had applications in signal processing and cryptosystems for multiplying and squaring numbers.

3. Is Karatsuba Algorithm the fastest way to multiply two numbers?

There have been many faster algorithms that developed after Karatsuba Algorithm. The current best is an O(Nlog(N)) algorithm to multiply two numbers developed by David Harvey and Joris van der Hoeven. You can read about the O(Nlog(N)) algorithm here.

An O(log(N)) memory version of the Karatsuba algorithm also exists, and the possibilities for improvement are still open.

Key Takeaways

The article helps us understand one of the essential and fundamental applications of divide and conquer algorithms .i.e., Karatsuba Algorithm. To understand the blog well, read a bit about Master's Theorem here and Divide and Conquer Algorithms here.

Learn more about the C++ STL library from here if you have trouble understanding some part of the code. Visit the link here for carefully crafted courses on campus placement and interview preparation on coding ninjas.

Recommended problems -

• Beautiful String
• Subsequence of a String
• Find the Shortest Substring in a String
   

Happy learning!