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
}
Random commentary about Machine Learning, BigData, Spark, Deep Learning, C++, STL, Boost, Perl, Python, Algorithms, Problem Solving and Web Search
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
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment