class for arbitrarily large integers
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 3 of 3

Thread: class for arbitrarily large integers

  1. #1
    Join Date
    Dec 2009
    Posts
    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?

  2. #2
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,273

    Re: class for arbitrarily large integers

    You could take a look at the implementation and C++ wrapper for GMP.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  3. #3
    Join Date
    Oct 2002
    Location
    Timisoara, Romania
    Posts
    14,360

    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.
    Marius Bancila
    Home Page
    My CodeGuru articles

    I do not offer technical support via PM or e-mail. Please use vbBulletin codes.

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
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center