Wednesday, May 30, 2012

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


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
}

No comments:

Post a Comment