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
- (Al * 10n/2 + Ar) * (Bl * 10n/2 + Br)
- Al * Bl * 10n + Al * Br * 10n/2 + Ar * Bl * 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:
- Al * Bl * 10n + Al * Br * 10n/2 + Ar * Bl * 10n/2 + Ar * Br
- Al * Bl * 10n + ((Al + Ar) * (Bl + Br) - (Al * Bl )- (Ar * Br)) * 10n/2 + Ar * Br
- 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.
- 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.
Following is the code implementation of the above algorithm.
- C++
- Java
- Python
- C#
- JavaScript
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;
}
You can also try this code with Online C++ Compiler
Java
import java.util.*;
public class Karatsuba {
public static String removeZerosFromFront(String a) {
for (int i = 0; i < a.length(); i++) {
if (a.charAt(i) != '0') {
return a.substring(i);
}
}
return "0";
}
public static String strAdd(String a, String b) {
if (a.length() > b.length()) {
String temp = a; a = b; b = temp;
}
int n = a.length();
int diff = b.length() - n;
StringBuilder ans = new StringBuilder();
int carry = 0;
for (int i = n - 1; i >= 0; i--) {
int sum_d = (a.charAt(i) - '0') + (b.charAt(i + diff) - '0') + carry;
carry = sum_d / 10;
ans.append(sum_d % 10);
}
for (int i = diff - 1; i >= 0; i--) {
int sum_d = (b.charAt(i) - '0') + carry;
carry = sum_d / 10;
ans.append(sum_d % 10);
}
if (carry != 0) {
ans.append(carry);
}
return ans.reverse().toString();
}
public static String singleDigMul(String b, char a) {
StringBuilder ans = new StringBuilder();
int d = a - '0', carry = 0;
for (int i = b.length() - 1; i >= 0; i--) {
int mul_d = (b.charAt(i) - '0') * d + carry;
carry = mul_d / 10;
ans.append(mul_d % 10);
}
if (carry != 0) ans.append(carry);
return ans.reverse().toString();
}
public static String karatsuba(String a, String b) {
if (a.length() > b.length()) {
String temp = a; a = b; b = temp;
}
int A = a.length(), B = b.length();
if (A == 1) return singleDigMul(b, a.charAt(0));
String copyA = "", copyB = "";
if (B % 2 != 0) {
copyB += '0';
B += 1;
}
for (int i = 0; i < B - A; i++) {
copyA += '0';
}
copyA += a;
copyB += b;
String A_l = copyA.substring(0, B / 2);
String A_r = copyA.substring(B / 2);
String B_l = copyB.substring(0, B / 2);
String B_r = copyB.substring(B / 2);
String I_1 = karatsuba(A_l, B_l);
String I_2 = karatsuba(A_r, B_r);
String I_3 = karatsuba(strAdd(A_l, A_r), strAdd(B_l, B_r));
I_3 = strAdd(I_3, strAdd(I_1, I_2));
I_1 += "0".repeat(B);
I_3 += "0".repeat(B / 2);
return removeZerosFromFront(strAdd(I_3, strAdd(I_1, I_2)));
}
public static void main(String[] args) {
String a = "907843";
String b = "578934";
String ans = karatsuba(a, b);
System.out.println(ans);
}
}
You can also try this code with Online Java Compiler
Python
def remove_zeros_from_front(a):
for i in range(len(a)):
if a[i] != '0':
return a[i:]
return "0"
def str_add(a, b):
if len(a) > len(b):
a, b = b, a
n = len(a)
diff = len(b) - n
ans = []
carry = 0
for i in range(n - 1, -1, -1):
sum_d = (ord(a[i]) - ord('0')) + (ord(b[i + diff]) - ord('0')) + carry
carry = sum_d // 10
ans.append(str(sum_d % 10))
for i in range(diff - 1, -1, -1):
sum_d = (ord(b[i]) - ord('0')) + carry
carry = sum_d // 10
ans.append(str(sum_d % 10))
if carry:
ans.append(str(carry))
return ''.join(ans[::-1])
def single_dig_mul(b, a):
ans = []
d = ord(a) - ord('0')
carry = 0
for i in range(len(b) - 1, -1, -1):
mul_d = (ord(b[i]) - ord('0')) * d + carry
carry = mul_d // 10
ans.append(str(mul_d % 10))
if carry:
ans.append(str(carry))
return ''.join(ans[::-1])
def karatsuba(a, b):
if len(a) > len(b):
a, b = b, a
A = len(a)
B = len(b)
if A == 1:
return single_dig_mul(b, a[0])
if B % 2 != 0:
b = '0' + b
B += 1
copy_A = '0' * (B - A) + a
copy_B = '0' * (B - len(b)) + b
A_l = copy_A[:B // 2]
A_r = copy_A[B // 2:]
B_l = copy_B[:B // 2]
B_r = copy_B[B // 2:]
I_1 = karatsuba(A_l, B_l)
I_2 = karatsuba(A_r, B_r)
I_3 = karatsuba(str_add(A_l, A_r), str_add(B_l, B_r))
I_3 = str_sub(I_3, str_add(I_1, I_2))
I_1 += '0' * B
I_3 += '0' * (B // 2)
return remove_zeros_from_front(str_add(I_3, str_add(I_1, I_2)))
if __name__ == "__main__":
a = "907843"
b = "578934"
ans = karatsuba(a, b)
print(ans)
You can also try this code with Online Python Compiler
C#
using System;
class Karatsuba {
static string RemoveZerosFromFront(string a) {
for (int i = 0; i < a.Length; i++) {
if (a[i] != '0') return a.Substring(i);
}
return "0";
}
static string StrAdd(string a, string b) {
if (a.Length > b.Length) {
var temp = a; a = b; b = temp;
}
int n = a.Length, diff = b.Length - n;
string ans = "";
int carry = 0;
for (int i = n - 1; i >= 0; i--) {
int sum_d = (a[i] - '0') + (b[i + diff] - '0') + carry;
carry = sum_d / 10;
ans += (sum_d % 10);
}
for (int i = diff - 1; i >= 0; i--) {
int sum_d = (b[i] - '0') + carry;
carry = sum_d / 10;
ans += (sum_d % 10);
}
if (carry != 0) ans += carry;
char[] arr = ans.ToCharArray();
Array.Reverse(arr);
return new string(arr);
}
static string SingleDigMul(string b, char a) {
string ans = "";
int d = a - '0', carry = 0;
for (int i = b.Length - 1; i >= 0; i--) {
int mul_d = (b[i] - '0') * d + carry;
carry = mul_d / 10;
ans += (mul_d % 10);
}
if (carry != 0) ans += carry;
char[] arr = ans.ToCharArray();
Array.Reverse(arr);
return new string(arr);
}
static string Karatsuba(string a, string b) {
if (a.Length > b.Length) {
var temp = a; a = b; b = temp;
}
int A = a.Length, B = b.Length;
if (A == 1) return SingleDigMul(b, a[0]);
if (B % 2 != 0) {
b = '0' + b;
B++;
}
string copyA = new string('0', B - A) + a;
string copyB = new string('0', B - b.Length) + b;
string A_l = copyA.Substring(0, B / 2);
string A_r = copyA.Substring(B / 2);
string B_l = copyB.Substring(0, B / 2);
string B_r = copyB.Substring(B / 2);
string I_1 = Karatsuba(A_l, B_l);
string I_2 = Karatsuba(A_r, B_r);
string I_3 = Karatsuba(StrAdd(A_l, A_r), StrAdd(B_l, B_r));
I_3 = StrAdd(I_3, StrAdd(I_1, I_2));
I_1 += new string('0', B);
I_3 += new string('0', B / 2);
return RemoveZerosFromFront(StrAdd(I_3, StrAdd(I_1, I_2)));
}
static void Main() {
string a = "907843";
string b = "578934";
string ans = Karatsuba(a, b);
Console.WriteLine(ans);
}
}
JavaScript
function removeZerosFromFront(a) {
for (let i = 0; i < a.length; i++) {
if (a[i] !== '0') {
return a.slice(i);
}
}
return "0";
}
function strAdd(a, b) {
if (a.length > b.length) {
[a, b] = [b, a];
}
let n = a.length;
let diff = b.length - n;
let ans = '';
let carry = 0;
for (let i = n - 1; i >= 0; i--) {
let sum_d = (a[i] - '0') + (b[i + diff] - '0') + carry;
carry = Math.floor(sum_d / 10);
ans += (sum_d % 10);
}
for (let i = diff - 1; i >= 0; i--) {
let sum_d = (b[i] - '0') + carry;
carry = Math.floor(sum_d / 10);
ans += (sum_d % 10);
}
if (carry) ans += carry;
return ans.split('').reverse().join('');
}
function singleDigMul(b, a) {
let ans = '';
let d = a - '0', carry = 0;
for (let i = b.length - 1; i >= 0; i--) {
let mul_d = (b[i] - '0') * d + carry;
carry = Math.floor(mul_d / 10);
ans += (mul_d % 10);
}
if (carry) ans += carry;
return ans.split('').reverse().join('');
}
function karatsuba(a, b) {
if (a.length > b.length) {
[a, b] = [b, a];
}
const A = a.length, B = b.length;
if (A === 1) return singleDigMul(b, a[0]);
if (B % 2 !== 0) {
b = '0' + b;
B++;
}
const copyA = '0'.repeat(B - A) + a;
const copyB = '0'.repeat(B - b.length) + b;
const A_l = copyA.slice(0, B / 2);
const A_r = copyA.slice(B / 2);
const B_l = copyB.slice(0, B / 2);
const B_r = copyB.slice(B / 2);
const I_1 = karatsuba(A_l, B_l);
const I_2 = karatsuba(A_r, B_r);
const I_3 = karatsuba(strAdd(A_l, A_r), strAdd(B_l, B_r));
I_3 = strAdd(I_3, strAdd(I_1, I_2));
I_1 += '0'.repeat(B);
I_3 += '0'.repeat(B / 2);
return removeZerosFromFront(strAdd(I_3, strAdd(I_1, I_2)));
}
const a = "907843";
const b = "578934";
const ans = karatsuba(a, b);
console.log(ans);
You can also try this code with Online Javascript Compiler
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++
Frequently Asked Questions
What is the recurrence equation of the Karatsuba algorithm?
The recurrence equation for the Karatsuba algorithm is T(n)=3T(n2)+O(n)T(n) = 3T\left(\frac{n}{2}\right) + O(n)T(n)=3T(2n​)+O(n). This represents the three recursive multiplications of half the size, combined with a linear time complexity for addition and other operations.
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.
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.
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.
Conclusion
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.
Recommended problems -
Happy learning!
86+ registered 