Interview Question

Anonymous Interview Menlo Park, CA

Given 2 very large numbers, each of which is so large it

  can only be represented as an array of integers, write a function to multiply them.
Answer

Interview Answer

3 Answers

2

This is similar to implementing add, subtract or multiply functions.

A good way to do this is use the same mechanism as we do in high school on paper i.e. you have two arrays. Put one as multiplier and the other as multiplicant.

Take the right most digit of multiplier, and multiply with last digit of multiplicant, assign the right into start of result (we either reverse result in the end or we assign it in the end of result ensuring result array's size can accommodate number of digits that result from the multiplication.

So we have two nested loops, outer one going through each digit of multiplier and inner one going through each of multiplicant.

There are special things to cater

1. Carry result of each multiplication to the next.
2. As in standard multiplication each next digit of multiplier results in as many digits of result for e.g. when multiplying 778 with 64 there is one row of results obtained when 4 is multiplied with each of 7,7 and 8 and another row when the same is done with 6. So either we store all these rows first and add corresponding indexes latter or we keep adding them into the final array as we go (without storing them separately)

Fayyaz on May 26, 2012
0

I just coded this too out of curiosity since i only coded big integer + and - in university which was like 6 years ago. So thought of making sure i was right. Here is the function and sample main call.

One thing i only found while debugging that two possibilities of carry exist
1. When simply the result of multiplying two numbers
2. When adding a result into existing array.

I missed 2 in my implementation at first and only discovered this through testing. Now it's resolved and working.

void multiply(int a[], int b[], int sa, int sb)
{
    int sr = sa+sb;
    int *r = new int[sr];
    int res_indx = sr-1;

    memset(r,0, sr * sizeof(int));
    //for(int i=0; i<sr; i++)
    // r[i] = 0;

    for(int mul=sa-1; mul>=0; mul--)
    {
        int c_indx = res_indx;
        int carry = 0;
        for(int mcnt=sb-1; mcnt>=0; mcnt--)
        {
            int m = b[mcnt] * a[mul] + carry;
            int sum = r[c_indx] + (m%10);
            r[c_indx--] = sum%10;
            carry = sum/10 + m/10; // two possibilities of carry one in the m and the other in sum

            if(mcnt == 0)
                r[c_indx] += carry; // copy the carry digit for the last operand
        }
        res_indx--; // X.. moving starting index one column back in each iteration
    }

    for(int i=0; i<sr; i++)
        cout << r[i];
    cout << endl;
}

int main()
{
    int a[] = {9,8,7,6,5,1,0};
    int b[] = {4,3,2,4,5,6,7};

    multiply(a, b, sizeof(a)/sizeof(int), sizeof(b)/sizeof(int));
        return 0;
}

Fayyaz on May 26, 2012
0

const unsigned MULTIPLY_BASE = 10;

void multiplyLittleEndian(const vector<unsigned> &a, const vector<unsigned> &b, vector<unsigned> &r)
{
    r.assign(a.size()+b.size(), 0);
    unsigned ri=0;
    for(unsigned ai=0; ai<a.size(); ++ai)
    {
        unsigned cri = ri++, carry = 0, am = a[ai], cr;
        for(unsigned bi=0; bi<b.size(); ++bi, ++cri)
        {
            cr = carry + am*b[bi] + r[cri];
            r[cri] = cr % MULTIPLY_BASE;
            carry = cr / MULTIPLY_BASE;
        }
        while(carry)
        {
            cr = carry + r[cri];
            r[cri++] = cr % MULTIPLY_BASE;
            carry = cr / MULTIPLY_BASE;
        }
    }
    while((!r.empty()) && r.back() == 0) r.pop_back(); // trim result
}

emk on Aug 30, 2012

Add Answers or Comments

To comment on this question, Sign In with Facebook or Sign Up