
December 10th, 2009, 10:28 PM
#1
class for arbitrarily large integers
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?

December 10th, 2009, 11:05 PM
#2
Re: class for arbitrarily large integers
You could take a look at the implementation and C++ wrapper for GMP.

December 11th, 2009, 08:58 AM
#3
Re: class for arbitrarily large integers
Other implementations:
http://mattmccutchen.net/bigint/
http://sourceforge.net/projects/cppbigint/
You have to be careful about how you implement the operations. Here is an algorithm for multiplication: http://en.wikipedia.org/wiki/Karatsuba_algorithm.
Tags for this Thread
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
