Question

1. Implement the faster algorithm for integer multiplication in C++ as a function, called “multiply”, that takes 2 unsigned integers and returns their multiplication as an unsigned integer.

2. Test your code in main.

Hints: Represent integers as strings.

Write a utility function that pads integers with zeros, this will be useful If the 2 integers differ in length In calculating ??10^? and (??+??) 10^(?/2)

Answer 1

Karatsuba algorithm is the faster algorithm for integer multiplication. We recursively divide our numbers into two halves until they are small enough to be multiplied using the naive multiplication method.

Numbers X and Y are split into Xl,Xr,Yl,Yr where Xl contains the first half (leftmost n/2) bits of X and Xr contains the second half (rightmost n/2) bits of X. Similarly Yl contains the first half (leftmost n/2) bits of Y and Yr contains the second half (rightmost n/2) bits of Y.

X =  Xl*2n/2 + Xr
Y =  Yl*2n/2 + Yr

So the product XY becomes

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

Since big integer arithmetic is not supported by C++, we represent our numbers as string.

C++ code:

#include <iostream>
#include <string>

//Macro to calculate the bigger value
#define max(a,b) ((a) > (b) ? (a) : (b))

using namespace std;

string add(string lhs, string rhs) 
{
    int length = max(lhs.size(), rhs.size());
    int carry = 0;
    int sum_col;  // sum of two digits in the same column
    string result;

    //padding shorter integer with 0's
    while (lhs.size() < length) 
      lhs.insert(0,"0");
            
    while (rhs.size() < length) 
      rhs.insert(0,"0");

    // build result string from right to left
    for (int i = length-1; i >= 0; i--) {
      sum_col = (lhs[i]-'0') + (rhs[i]-'0') + carry;
      carry = sum_col/10;
      result.insert(0,to_string(sum_col % 10));
    }
    
    if (carry)
      result.insert(0,to_string(carry));
    
    //extra 0's are removed
    return result.erase(0, min(result.find_first_not_of('0'), result.size()-1));
}

string subtract(string lhs, string rhs) {
    int length = max(lhs.size(), rhs.size());
    int diff;
    string result;
        
        //padding with 0's
    while (lhs.size() < length) 
      lhs.insert(0,"0");
       
    while (rhs.size() < length) 
      rhs.insert(0,"0");

    for (int i = length-1; i >= 0; i--) {
        diff = (lhs[i]-'0') - (rhs[i]-'0');
        if (diff >= 0)
            result.insert(0, to_string(diff));
        else {

            int j = i - 1;
            while (j >= 0) {
                lhs[j] = ((lhs[j]-'0') - 1) % 10 + '0';
                if (lhs[j] != '9') 
                    break;
                else 
                    j--;
            }
            result.insert(0, to_string(diff+10));
        }
      
    }
        //removing leading 0's
    return result.erase(0, min(result.find_first_not_of('0'), result.size()-1));
}

string multiply(string lhs, string rhs) {
    int length = max(lhs.size(), rhs.size());
    
    while (lhs.size() < length) 
      lhs.insert(0,"0");

    while (rhs.size() < length) 
      rhs.insert(0,"0");

    if (length == 1)
        return to_string((lhs[0]-'0')*(rhs[0]-'0'));

    string lhs0 = lhs.substr(0,length/2);
    string lhs1 = lhs.substr(length/2,length-length/2);
    string rhs0 = rhs.substr(0,length/2);
    string rhs1 = rhs.substr(length/2,length-length/2);
    
    string p0 = multiply(lhs0,rhs0);
    string p1 = multiply(lhs1,rhs1);
    string p2 = multiply(add(lhs0,lhs1),add(rhs0,rhs1));
    string p3 = subtract(p2,add(p0,p1));

    for (int i = 0; i < 2*(length-length/2); i++)
        p0.append("0");
    for (int i = 0; i < length-length/2; i++)
        p3.append("0");
        
    string result = add(add(p0,p1),p3);

    return result.erase(0, min(result.find_first_not_of('0'), result.size()-1));
}

int main() {
    string s1, s2;
    s1="897999802";
    s2="2289311938";
    cout << multiply(s1,s2) << endl;
    return 0;
}

Output for your reference: