**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:

- A * B
- (A
_{l} * 10^{n/2} + A_{r}) * (B_{l} * 10^{n/2} + B_{r})
- A
_{l}^{ }* B_{l} * 10^{n} + 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^{2}).

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^{2}) we’ll try to change the above equation using a bit of algebra in the following way:

- A
_{l}^{ }* B_{l} * 10^{n} + A_{l} * B_{r} * 10^{n/2} + A_{r} * B_{l }* 10^{n/2} + A_{r} * B_{r}
- A
_{l}^{ }* B_{l} * 10^{n} + ((A_{l} + A_{r}) * (B_{l} + B_{r}) - (A_{l}^{ }* B_{l} )- (A_{r} * B_{r})) * 10^{n/2} + A_{r} * B_{r}
- E_1 * 10
^{n} + (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^{n} 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.

- 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.
- 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.
- 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^{2} + N/2^{3} +.....+ 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 -**

Happy learning!