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