KaratSuba's Algorithm

Integer Multiplication can be achieved using O(n ^ 1.59) using this faster algorithm.

// 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 ) // 0, 1
{
	string result; // To store the sum bits

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

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

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

		// boolean expression for 3-bit addition
      // carry = (0 & 1) | (1 & )
		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);
    string re1 = addBitStrings(Xl, Xr);
   string re2 = addBitStrings(Yl, Yr);
   cout << " P1 "<< P1 << " P2 " << P2 << " re1 " << re1 << " re2 " << re2 << endl;
	long int P3 = multiply(re1, re2);
    long int fin = P1*(1<<(2*sh)) + (P3 - P1 - P2)*(1<<sh) + P2;\
      cout << " final "<< fin <<endl;
	// Combine the three products to get the final result.
	return fin;
}

// 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"));
}

Output 

P1 0 P2 0 re1 1 re2 1
 final 2
 P1 1 P2 0 re1 1 re2 1
 final 4
 P1 2 P2 4 re1 11 re2 100
 P1 0 P2 0 re1 10 re2 0
 P1 0 P2 0 re1 1 re2 0
 final 0
 final 0
 P1 0 P2 0 re1 11 re2 01
 P1 0 P2 1 re1 10 re2 1
 P1 0 P2 0 re1 1 re2 1
 final 2
 final 3
 final 12
 final 60
60

The multiply recursive function is explained visually in whiteboard.