Divide and Conquer | Set 4 (Karatsuba algorithm for fast multiplication) | GeeksforGeeks

Given two binary strings that represent value of two integers, find the product of two strings.

For simplicity let us assume that n is even

X =  Xl*2n/2 + Xr    [Xl and Xr contain leftmost and rightmost n/2 bits of X]
Y =  Yl*2n/2 + Yr    [Yl and Yr contain leftmost and rightmost n/2 bits of Y]

The product XY can be written as following.

XY = (Xl*2n/2 + Xr)(Yl*2n/2 + Yr)
   = 2n XlYl + 2n/2(XlYr + XrYl) + XrYr

If we take a look at the above formula, there are four multiplications of size n/2, so we basically divided the problem of size n into for sub-problems of size n/2. But that doesn’t help because solution of recurrence T(n) = 4T(n/2) + O(n) is O(n^2). The tricky part of this algorithm is to change the middle two terms to some other form so that only one extra multiplication would be sufficient. The following is tricky expression for middle two terms.

XlYr + XrYl = (Xl + Xr)(Yl + Yr) - XlYl- XrYr

So the final value of XY becomes

XY = 2n XlYl + 2n/2 * [(Xl + Xr)(Yl + Yr) - XlYl - XrYr] + XrYr

With above trick, the recurrence becomes T(n) = 3T(n/2) + O(n) and solution of this recurrence is O(n^1.59).

What if the lengths of input strings are different and are not even? To handle the different length case, we append 0′s in the beginning. To handle odd length, we put floor(n/2) bits in left half and ceil(n/2)bits in right half. So the expression for XY changes to following.

XY = 22ceil(n/2) XlYl + 2ceil(n/2) * [(Xl + Xr)(Yl + Yr) - XlYl - XrYr] + XrYr

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;

}

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;

}

int multiplyiSingleBit(string a, string b)

{  return (a[0] - '0')*(b[0] - '0');  }

A Naive Approach is to one by one take all bits of second number and multiply it with all bits of first number. Finally add all multiplications. 
Read full article from Divide and Conquer | Set 4 (Karatsuba algorithm for fast multiplication) | GeeksforGeeks