karatsuba algorithm for big integer multiplication

By
Home » Programming » C++ Programming » karatsuba algorithm for big integer multiplication

Do you know that the naive way of multiplication of two numbers takes O(nˆ2) run time? Today, I will show you one algorithm which runs better than naive multiplication. It is called karatsuba algorithm. The karatsuba algorithm is one of the fast ways of multiplying the two big integer numbers. It was discovered by Anatoly Karatsuba in 1960 and later it was published in 1962.

Karatsuba algorithm for fast multiplication

How does the karatsuba algorithm work? Given two numbers x and y of size ‘n’, these are the steps that you have to follow to multiply it.

  1. Divide the numbers x and y into two equal half. Let’s indicate the two half of x as x_left and x_right. Similarly for y as y_left and y_right.
  2. Multiply x_left with y_left value.
  3. Find the sum of x_left and x_right,  y_left and y_right, and then multiply the two sum.
  4. Multiply the x_right and y_right values.
  5. Subtract the value from (step3 – step2 – step5).
  6. Finally, add the value of (step2 + step4 + step5) with appropriate padding of zero.

When the size of x and y is large, we can solve it recursively by calling the karatsuba algorithm.

Pseudocode for the karatsuba algorithm

Let’s define the user input and output for the program code.

Input: number x and y

Output: display the product of x and y

//x and y are the two numbers to multiply
Algorithm karatsuba(x,y){
    if(x < 10 and y < 10) then
        return x * y
    x_left, x_right = x[0:n/2], x[n/2:n]
    y_left, y_right = y[0:n/2], y[n/2:n]
    p1 = karatsuba(x_left, y_left)
    p2 = karatsuba(x_left + x_right, y_left + y_right)
    p3 = karatsuba(x_right, y_right)
   
    return (p1*10^n) + ((p2-p1-p3 )*10^n/2) + p3
}

You see the pseudocode looks very simple, but it is not that simple to implement in the programming language except in python programming. The main issue will come when the number is too big that the built-in data types are not sufficient to handle the numbers. So, one way to overcome this issue is to use the string to store the numbers and perform operations on the string.

Source code for karatsuba algorithm in C++

Since the integer data types can not hold the value of x, y, and its product when its size is very large. Let’s redefine the user input for the program code in c++.

Input: number x and y in string format

Output: display the product of x and y

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

string appendZero(string str, int n);
string karatsuba(string x, string y);
string multiplyXY(string x, string y);
string addXY(string x, string y);
string subtractXY(string x, string y);
string removeZero(string str);
string multiply10(string str, int n);

int main(){
	string x,y;
	getline(cin, x);
	getline(cin, y);
	if(x == "0" || y == "0"){
		cout << "0" << endl;
	}else{
		if(x.length() > y.length()){
			y = appendZero(y, x.length() - y.length());
		}else{
			x = appendZero(x, y.length() - x.length());
		}
		cout << removeZero(karatsuba(x,y))<< endl;
	}
	return 0;
}

string karatsuba(string x, string y){
	if(x.length() == 1 && y.length() == 1){
		return multiplyXY(x, y);
	}

	if(x.length() > y.length()){
		y = appendZero(y, x.length() - y.length());
	}else{
		x = appendZero(x, y.length() - x.length());
	}
	if(x.length()%2 !=0){
		x = "0" + x;
		y = "0" + y;
	}

	string x_left, x_right, y_left, y_right, p1, p2, p3;
	int n = x.length();

	x_left = x.substr(0, x.length()/2);
	x_right = x.substr(x.length()/2);
	y_left = y.substr(0, y.length()/2);
	y_right = y.substr(y.length()/2);
 	
	p1 = karatsuba(x_left, y_left);
	p2 = karatsuba(addXY(x_left, x_right), addXY(y_left, y_right));
	p3 = karatsuba(x_right, y_right);

	return addXY(addXY(multiply10(p1, n), multiply10(subtractXY(subtractXY(p2,p1), p3), n/2)), p3); 
}

string appendZero(string str, int n){
	while(n>0){
		str = "0" + str;
		n--;
	}
	return str;
}
string multiplyXY(string x, string y){
	int product;
	product = ((int)x[0] - '0') * ((int)y[0] - '0');
	return to_string(product);
}

string addXY(string x, string y){
	if(x.length() > y.length()){
		y = appendZero(y, x.length() - y.length());
	}else{
		x = appendZero(x, y.length() - x.length());
	}
	int carry = 0, sum;
	string result = "";
	for(int i = x.length() - 1; i >= 0; i--){
		sum = ((int)x[i] - '0') + ((int)y[i] - '0') + carry;

		if(sum > 9){
			result = to_string(sum%10) + result;
			carry = sum/10;
		}else{
			result = to_string(sum) + result;
			carry = 0;
		}
	}
	if(carry != 0){
		result = to_string(carry) + result;
	}
	return result;
}

string subtractXY(string x, string y){
	if(x.length() > y.length()){
		y = appendZero(y, x.length() - y.length());
	}else{
		x = appendZero(x, y.length() - x.length());
	}

	string result = "";
	int borrow = 0, a, b;
	for(int i = x.length() - 1; i>=0; i--){
		a = (int)x[i] - '0';
		b = (int)y[i] - '0';
		if(borrow == 1){
			a = a - 1;
		}
		if(a >= b){
			result = to_string(a - b) + result;
			borrow = 0;
		}else{
			a = a + 10;
			result = to_string(a - b) + result;
			borrow = 1;
		}
	}
	return removeZero(result);
}

string removeZero(string str){
	reverse(str.begin(), str.end());
	for(int i = str.length() - 1; i >= 0; i--){
		if(str[i] == '0'){
			str.pop_back();
		}else{
			break;
		}
	}
	if(str.empty()){
		return "0";
	}else{
		reverse(str.begin(), str.end());
		return str;
	}	
}

string multiply10(string str, int n){
	while(n>0){
		str = str + "0";
		n--;
	}
	return str;
}

In order to implement the karatsuba algorithm, I have used many subroutines so that the code looks more intuitive to understand. The user-defined functions used in the above algorithm are as follows:

  1. appendZero(): It is used to append zero at the front so that the length of two number strings can be of the same size.
  2. multiplyXY(): It is used to multiply two single-digit string numbers.
  3. addXY(): It is used to add two big integer strings.
  4. subtractXY(): It is used to subtract two big integer strings.
  5. removeZero(): It is used to remove unwanted zero from the integer string.
  6. multiply10(): It is used to multiply an integer string by a multiple of 10.

Run time complexity of the algorithm.

Since the karatsuba algorithm is solved using the recursion algorithm. Its recursive relation can be written as

T(n) = 3T(n/2) + c.n

When we solve the above recursive relation, we get the run time as O(n^1.58) or O(n^log3).

Conclusion

Now you know that the naive multiplication will take a run time of O(n^2). But we can multiply the two numbers faster using the karatsuba algorithm which takes only O(n^1.58) as its run time. There is another algorithm as well which runs faster than karatsuba algorithm, namely the Toom-Cook algorithm(O(n^1.46)) and Schönhage–Strassen algorithm(O(nlogn loglog n)).

Read About