class for arbitrarily large integers

[sagredo]

Hi all,

I've been working on sorting out a problem that I often get asked on quantitative interviews, and wondering if you could help me get a fix on it.

The problem is to create a class that allows operations to be performed on arbitrarily large integers.

I'm working on the input/output portion right now & having a little bit of a problem.

The way I see it, the best way to attack this would be to use a vector<unsigned char> to get a reversed string:

class LargeInteger
{
...

private:
std::vector<unsigned char> digits;
bool minus;

};


Then read the number as a string by using getline(cin, strInput);

Then, use a reverse iterator to check each digit and add it (e. g. by calling push_back) to the internal vector (or string) if ok. The input at first position (position 0 or last of reverse iteration alternatively can be a minus sign).

string::reverse_iterator ri;
for (ri = strInput.rbegin(); ri != strInput.rend(); ++ri)
{
char digit = *ri;
// now check the digit and if ok convert it to an 8bit integer
// by subtracting '0' and push it to the internal vector
// handle the *last* char separately as it could be a minus sign
// in that case you would *not* push it to the vector but set the
// minus member to true.
// you also might ignore leading spaces or a + sign.

...
}

What I'm having trouble with now is putting it all together, or simply implementing it all in code form. Could anyone give me a hand?

[laserlight]

You could take a look at the implementation and C++ wrapper for GMP.

[cilu]

Other implementations:
http://mattmccutchen.net/bigint/
http://sourceforge.net/projects/cpp-bigint/

You have to be careful about how you implement the operations. Here is an algorithm for multiplication: http://en.wikipedia.org/wiki/Karatsuba_algorithm.