karatsub.cpp

// C++ implementation of Karatsuba algorithm for bit string multiplication. 
#include<iostream> 
#include<stdio.h> 

using namespace std; 

// FOLLOWING TWO FUNCTIONS ARE COPIED FROM http://goo.gl/q0OhZ 
// Helper method: given two unequal sized bit strings, converts them to 
// same length by adding leading 0s in the smaller string. Returns the 
// the new length 
int makeEqualLength(string &str1, string &str2) 
{ 
	int len1 = str1.size(); 
	int len2 = str2.size(); 
	if (len1 < len2) 
	{ 
		for (int i = 0 ; i < len2 - len1 ; i++) 
			str1 = '0' + str1; 
		return len2; 
	} 
	else if (len1 > len2) 
	{ 
		for (int i = 0 ; i < len1 - len2 ; i++) 
			str2 = '0' + str2; 
	} 
	return len1; // If len1 >= len2 
} 

// The main function that adds two bit sequences and returns the addition 
string addBitStrings( string first, string second ) 
{ 
	string result; // To store the sum bits 

	// make the lengths same before adding 
	int length = makeEqualLength(first, second); 
	int carry = 0; // Initialize carry 

	// Add all bits one by one 
	for (int i = length-1 ; i >= 0 ; i--) 
	{ 
		int firstBit = first.at(i) - '0'; 
		int secondBit = second.at(i) - '0'; 

		// boolean expression for sum of 3 bits 
		int sum = (firstBit ^ secondBit ^ carry)+'0'; 

		result = (char)sum + result; 

		// boolean expression for 3-bit addition 
		carry = (firstBit&secondBit) | (secondBit&carry) | (firstBit&carry); 
	} 

	// if overflow, then add a leading 1 
	if (carry) result = '1' + result; 

	return result; 
} 

// A utility function to multiply single bits of strings a and b 
int multiplyiSingleBit(string a, string b) 
{ return (a[0] - '0')*(b[0] - '0'); } 

// The main function that multiplies two bit strings X and Y and returns 
// result as long integer 
long int multiply(string X, string Y) 
{ 
	// Find the maximum of lengths of x and Y and make length 
	// of smaller string same as that of larger string 
	int n = makeEqualLength(X, Y); 

	// Base cases 
	if (n == 0) return 0; 
	if (n == 1) return multiplyiSingleBit(X, Y); 

	int fh = n/2; // First half of string, floor(n/2) 
	int sh = (n-fh); // Second half of string, ceil(n/2) 

	// Find the first half and second half of first string. 
	// Refer http://goo.gl/lLmgn for substr method 
	string Xl = X.substr(0, fh); 
	string Xr = X.substr(fh, sh); 

	// Find the first half and second half of second string 
	string Yl = Y.substr(0, fh); 
	string Yr = Y.substr(fh, sh); 

	// Recursively calculate the three products of inputs of size n/2 
	long int P1 = multiply(Xl, Yl); 
	long int P2 = multiply(Xr, Yr); 
	long int P3 = multiply(addBitStrings(Xl, Xr), addBitStrings(Yl, Yr)); 

	// Combine the three products to get the final result. 
	return P1*(1<<(2*sh)) + (P3 - P1 - P2)*(1<<sh) + P2; 
} 

// Driver program to test above functions 
int main() 
{ 
	printf ("%ld\n", multiply("1100", "1010")); 
	printf ("%ld\n", multiply("110", "1010")); 
	printf ("%ld\n", multiply("11", "1010")); 
	printf ("%ld\n", multiply("1", "1010")); 
	printf ("%ld\n", multiply("0", "1010")); 
	printf ("%ld\n", multiply("111", "111")); 
	printf ("%ld\n", multiply("11", "11")); 
}