New datatype which can have numbers upto 100 digits.

Question

Note: This was an interview question and may not have an actual use case currently

The question was to design a class that can store numbers which are very very large say each number can have 100 digits. This new class is a datatype like int.

What are the different types of constructors, overloads and other functions that you would write.

How can this be further extended to support really large floating point numbers.

How this can be given to others so that they can reuse the same component with their own additional functionality.

My answer consisted of 2 approaches 1. using array of integers to store every say 10 digits 2. using string itself to store the number and perform operations on individual numbers.

What would be the best approach?

Answer 1

The best approach would be to propose they use am existing, tried and tested C++ wrapper for a bignum library like GMP.

Answer 2

See Wikipedia article about Arbitrary-precision arithmetic.

Answer 3

Nice question :)

First of all, using a string representation is just not professional. You can do the mathematical operations at the level the word of the machine instead much more efficiently. Especially if you are going to use base 2.

What are the different types of constructors, overloads and other functions that you would write.

You need a set of constructors like a default one, copy constructor, construction from native integer types. The last part is the tricky part actually in C++, mixing signed/unsigned arithmetic in C++ is not so-simple as it looks like. You can benefit from this video by the creators of safeint(used by Microsoft). Also, you could need to construct your bignum from raw memory(byte-block). A destructor would be needed if your bignum is dynamic, otherwise it is trivial to implement.

Input/Ouput standard facilities are a must for such a library to ease using it. Providing a way to accept numbers in popular bases is a plus also. For the operations, your type should behave just like simple native type. This means you need to overload almost all the operators that you could overload:

Arithmetic operators
Comparison operators/Relational operators
Logical operators
Bitwise operators
Compound-assignment operators
etc..

The content of the library is an open-ended question.

The most important thing to remember is that C++ has some weired rules concerning the conversion between signed and unsigned numbers. Care must taken!

How can this be further extended to support really large floating point numbers.

big floats are not that easy. Basically, you choose the radix you want to work with. Representing the number scientifically means having base and exponent parts. Which are integers in fact.

How this can be given to others so that they can reuse the same component with their own additional functionality.

Try to make it non-intrusive. i.e. when I take int off, and put instead of it my_bigint, then it should work! typedeffing should be just enough to switch between your type and native types. Let others write functions on top of the type, make it a black box. I prefer headers when using libraries, so I would write the library header-only.

My answer consisted of 2 approaches 1. using array of integers to store every say 10 digits 2. using string itself to store the number and perform operations on individual numbers.

Strings are not really suitable. What you need is to choose base 2**n as your base in most cases. There are libraries which use other bases, but it is not a good idea in my opinion, MAPM is one of those.

Answer 4

I myself implemented a bigint class for solving a code-jam problem. I used unsigned array to store the values but you need to maintain the number of digits separately. I implemented it based on the need,

#define BIG_INT_SIZE 100

class BigInt
{
    friend ostream& operator<< (ostream& out, const BigInt& arg);
    friend istream& operator>> (istream& inp,       BigInt& arg);

    private:
            unsigned num[BIG_INT_SIZE+1];
            unsigned digits;
            bool     sign; // true for -ve

    public:
            BigInt(const char* = NULL) throw();
            BigInt(const BigInt&) throw();
            ~BigInt() throw();

            // ASSIGNMENT OPERATORS
            BigInt& operator=  (const BigInt& arg) throw();
            BigInt& operator=  (const    int& arg) throw();
            BigInt& operator=  (const   char* arg) throw();

            // ARITHMETIC OPERATORS
            BigInt  operator+  (const BigInt& arg) throw();
            BigInt  operator+= (const BigInt& arg) throw();
            BigInt  operator+  (const    int& arg) throw();
            BigInt  operator+= (const    int& arg) throw();

            BigInt  operator-  (const BigInt& arg) throw();
            BigInt  operator-= (const BigInt& arg) throw();
            BigInt  operator-  (const    int& arg) throw();
            BigInt  operator-= (const    int& arg) throw();

            BigInt  operator*  (const BigInt& arg) throw();
            BigInt  operator*= (const BigInt& arg) throw();
            BigInt  operator*  (const    int& arg) throw();
            BigInt  operator*= (const    int& arg) throw();

            BigInt  operator/  (const BigInt& arg) throw();
            BigInt  operator/= (const BigInt& arg) throw();
            BigInt  operator/  (const    int& arg) throw();
            BigInt  operator/= (const    int& arg) throw();

            BigInt  operator%  (const BigInt& arg) throw();
            BigInt  operator%= (const BigInt& arg) throw();
            BigInt  operator%  (const    int& arg) throw();
            BigInt  operator%= (const    int& arg) throw();

            // UNARY OPERATORS
            void operator++ ()    throw();
            void operator++ (int) throw();
            void operator-- ()    throw();
            void operator-- (int) throw();

            // COMPARISON OPERATORS
            bool   operator>  (const BigInt& arg) throw();
            bool   operator>= (const BigInt& arg) throw();
            bool   operator<  (const BigInt& arg) throw();
            bool   operator<= (const BigInt& arg) throw();
            bool   operator== (const BigInt& arg) throw();
            bool   operator!= (const BigInt& arg) throw();

            // DISPLAY & ORDERING
            void big_int_order() throw();
            void big_int_print() throw();
};

Hope this might be helpful. I will post the complete implementation in my blog. I will update as i am done.