1.
Introduction
2.
Problem Statement
3.
Approach
4.
Code in C++
4.1.
Output
4.2.
Time Complexity
4.3.
Space Complexity
5.
6.
Key Takeaways
Last Updated: Mar 27, 2024

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

SHIKHAR SONI

## Introduction

We learned to multiply two decimal numbers back in first grade. If we have two N digit numbers, we would need to multiply each digit with every digit of the other number, making our school grade algorithm’s complexity O(N2). This article will explore a technique that guarantees a time complexity less than the above one using a divide and conquer algorithm.

Also see, Euclid GCD Algorithm

## Problem Statement

We are given two decimal numbers with a large number of digits (up to 105) as strings, and we need to write an efficient algorithm to find and print their product.

For example,

``````Input 1: a = "1234", b="98765"
Output 1: "121876010"

Input 2: a = "174592649246", b = "5542636194655762654"
Output 2: "967703537031717748762448058884"``````

## 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. (Al * 10n/2 + Ar) * (Bl * 10n/2 + Br)
3. Al * Bl * 10n + Al * Br * 10n/2 + Ar * B* 10n/2 + Ar * Br

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 (Al and Ar 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(N2).

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

1. Al * Bl * 10n + Al * Br * 10n/2 + Ar * B* 10n/2 + Ar * Br
2. Al * Bl * 10n + ((Al + Ar) * (Bl + Br) - (Al * Bl )- (Ar * Br)) * 10n/2 + Ar * Br
3. E_1 * 10n + (E_2 - E_1 - E_3) * 10n/2 + E_3, where E_1 = (Al * Bl), E_2 = ((Al + Ar) * (Bl + Br)) and E_3 = (Ar * Br)

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 10n or 10n/2 take O(N) time.

Hence we obtain a new recurrence, T(N) = 3 * T(N/2) + O(N). Solving this yields O(Nlog2(3)), which is approximately equal to O(N1.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";
}
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) 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)
// Al * Bl + Ar * Br
// (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)

// 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(N1.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/22 + N/23 +.....+ N/2d (< 2*N).

Also check out - Substr C++

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!

Live masterclass