-
December 10th, 2009, 11: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 11th, 2009, 12:05 AM
#2
Re: class for arbitrarily large integers
You could take a look at the implementation and C++ wrapper for GMP.
-
December 11th, 2009, 09:58 AM
#3
Re: class for arbitrarily large integers
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.
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
|