How to perform BigInteger multiplication on char vectors?

Question

I'm implementing a BigInt in c++ and am trying to overload the multiplication operator. I'm storing large integers in a char vector.

vector<char> storage;

Here is what I did to implement operator*(int)

BigInt BigInt::operator*(int x)
{
int extra = 0;
int dec_mod = pow(10, this->storage.size());

for (auto & g : storage) {
    g = g * x + extra;
    int mod_g = g % dec_mod;
    extra = g / dec_mod;
    g = mod_g;
}

while (extra > 0) {
    storage.push_back(extra % dec_mod);
    extra /= dec_mod;
}

return *this;
}

The operator*(bigInt) function returns wrong answers. For example, 33 * 4 returns 1212 and not 132.This was my attempt at writing the overloaded operator* which takes a bigint object:

BigInt BigInt::operator*(BigInt bigN) {
int carry = 0;

for (int i = bigN.storage.size()-1; i >= 0; i--) {

    for (int j = this->storage.size()-1; j >= 0; j--) {

        int val = (this->storage.at(i) * bigN.storage.at(j)) + carry;
        this->storage.push_back(val % 10);
        carry = val / 10;
    }

}
return *this;
}

It looks like the logic in the carry is flawed, but i'm not sure how to fix it.

Warning: `pow` operates in floating point. You may get truncation errors due to lack of precision in larger numbers. On a less vital note, `pow` is designed to compute stuff like e to the power of pi and is usually vast overkill for computing the power of integers. A simple loop that multiplies is often faster in addition to safer ( no truncation issues) — user4581301, Apr 18 '18 at 22:47
You do multiplication of big integers just like you learnt to do long multiplication in school. Get a pencil and paper and multiply 123*456. Do it exactly the same way on the computer. Do not use any library functions as they are not needed. — Richard Critten, Apr 18 '18 at 22:51
To best solve this problem, step through the code in question either on paper (following your coded instructions to the letter) or with the debugging software that almost certainly came with your C++ development environment to watch where errors occur. — user4581301, Apr 18 '18 at 22:52
Usage of `pow` almost makes the whole attempt null and void, given the [issues with pow](https://stackoverflow.com/questions/25678481/why-does-pown-2-return-24-when-n-5-with-my-compiler-and-os). — PaulMcKenzie, Apr 18 '18 at 22:55

score 0 · Answer 1 · answered Apr 19 '18 at 03:22

I'm not sure how you're trying to do this, but here is a walkthrough of why you're getting the result 1212 instead of 132:

BigInt operator*(int x)// x is 4
    {
        // Let's say storage holds 33, that's
        // {3, 3} in your char vector;
        int extra = 0;
        int dec_mod = pow(10, this->storage.size()); // dec_mod may be 100


        for (auto & g : storage) 
        {
            g = g * x + extra;  // same as g = 3 * 4 + 0, g = 12
            int mod_g = g % dec_mod; // same as mod_g = 12 % 100 = 12
            extra = g / dec_mod; // same as 12 / 100 = 0
            g = mod_g;  // g = 12
        }
        // Exact same thing happens on the second iteration, your storage vector
        // ends up as {12, 12};
        // That's why your result is 1212

        while (extra > 0) {
            storage.push_back(extra % dec_mod);
            extra /= dec_mod;
        }
        return *this;
    }

I'm not sure how you are trying to do it, but here's my attempt, it's just as one would do it on paper:

#include <iostream>
#include <string>
#include <vector>

using namespace std;

struct BigInt
{
    BigInt(std::string num) { for (auto &i : num) storage.push_back(i - 48); }
    BigInt(std::vector<char> numVect) : storage(numVect) {}

    vector<char> storage;

    string getAsString() 
    { string str; for (auto& i : storage) str += i + 48; return str; }
    // Add 48 to turn 0 - 9 to ascii string.

    vector<char> add(vector<char>& lhs, vector<char>& rhs)
    // Add function only needed if number is multiplied by more than one digit.
    {
        // Fill with zeros to make both vectors same length.
        int sizeDiff = (int)lhs.size() - (int)rhs.size();
        if (sizeDiff < 0)
            lhs.insert(lhs.begin(), abs(sizeDiff), 0);
        else if (sizeDiff > 0)
            rhs.insert(rhs.begin(), abs(sizeDiff), 0);

        vector<char> resultVect;
        int carry = 0;
        for (int i = lhs.size() - 1; i >= 0; --i)
        {
            int result = lhs[i] + rhs[i] + carry;
            carry = result / 10;
            result %= 10;
            resultVect.insert(resultVect.begin(), result);
        }
        if (carry != 0) resultVect.insert(resultVect.begin(), carry);

        return resultVect;
    }

    BigInt operator*(BigInt rhs)
    {
        int unitPlace = 0; // Keeps track of how many zeros to add in subsequent results
        vector<char> totalVect; // Accumulated value after each addition
        vector<char> resultVect; // Result of this particular multiplication

        for (int i = rhs.storage.size() - 1; i >= 0; --i, unitPlace++)
        {
            int carry = 0;
            for (int k = 0; k < unitPlace; ++k) resultVect.push_back(0);

            for (int j = storage.size() - 1; j >= 0; j--)
            {
                int result = rhs.storage[i] * storage[j] + carry;
                carry = result / 10;
                result %= 10;

                resultVect.insert(resultVect.begin(), result);
            }
            resultVect.insert(resultVect.begin(), carry);
            totalVect = add(totalVect, resultVect); // Add sub-result
            resultVect.clear();
        }

        // Strip leading zeros
        for (int i = 0; i < totalVect.size(); ++i) {
            if (totalVect[i] == 0) totalVect.erase(totalVect.begin() + i);
            else break;
        }

        return BigInt{ totalVect };
    }
};

int main()
{
    BigInt a{ "335467" };
    BigInt b{ "1019737" };

    BigInt c = a * b;

    std::cout << c.getAsString() << '\n';

    cin.ignore();
    return 0;
}

How to perform BigInteger multiplication on char vectors?

1 Answers1