Reduce memory footprint in the construction of a BigInt class

Question

I'm working on a concept at the moment and I'm writing the Pseudo code as I am asking this question. I'm thinking of making a fairly easy and simple to use class interface to represent BigInts. I'm thinking of making a couple of simple structures with basic properties and members that the BigInt class would use. For example instead of the BigInt class handling negative values directly it would contain a Sign struct and this struct would basically contain either a value of 0 or 1, or basically a Boolean type to designate if this BigInt is positive or negative. Upon Construction I intend to have the class generate a positive by default. I would also like to have a struct that represents the digits where there are two variants. The first variant has the digits 0-9 and the second which would inherit the original but also includes A-F. This way the class which would be a template class but only ever has two valid types would support use for Decimal and Hexadecimal. All of the mathematical operators would be defined outside of the class and depending its inferred type it will call and perform the appropriate version of the function. However the Hexadecimal part is still only concept as I'd like to get the Decimal version up and running first. These helper classes might look something like this:

class Sign {
private:
    bool isNegative_ { false };
    char sign_;
public:
    Sign() : isNegative_( false ) {
        sign_ = '+';
    }
    Sign( const bool isNegative ) : isNegative_( isNegative ) { 
        sign_ = isNegative_ ? '-' : '+';
    }; 

    Sign( const char sign ) {
        if ( sign == '+' || sign == '\0' || sign == ' ' ) {
            isNegative_ = false;
        } else if ( sign == '-' ) {
            isNegative_ = true;
        } else {
            // throw error improper character.
        }
    }

    bool isPostive() const { return !isNegative_; }
    bool isNegative() const { return !isNegative; }

    char sign() const { return sign_; }
    char negate() {
        isNegative_ = !isNegative_;
        sign_ = isNegative_ ? '+' : '-'; 
        return sign_;         
    }        
};

// NST = NumberSystemType
class enum NST { Decimal = 10, Hexadecimal = 16 };

template<class NT> // NT = NumberType
class Digit {
private:
    NST nst_; // determines if Decimal or Hexadecimal       
};

// Specialization for Decimal
template<NST::Decimal> // Should be same as template<10>
class Digit {
    // would like some way to define 4 bits to represent 0-9; prefer not to
    // use bitfields, but I think a char or unsigned char would be wasting 
    // memory using twice as much for what is needed. Not sure what to do here...
    // maybe std::bitset<>...


};

template<NST::Hexadecimal> // Should be same as template<16>
class Digit : public Digit<Decimal> { // Also inherits all of The first specialization.
    // same as above only needs 4 bits to represent values form 0-F
    // A half char would be excellent but does not exist in c++... and most
    // programming language's types.
    // still thinking of maybe std::bitset<>...

};

The main distinction between the two is that the first specialization would only allow digits values from 0-9 and the digits themselves 0-9 where the second doesn't have that restriction, but also allows from a-f and or A-F either case is valid. I may also include a const char* to designate the Hex Prefix of 0x that would be appended to any contained value for display.

I like this design approach as I'd like to keep the actual arithmetic functions and operators of the BigInt class as seperate function templates since the BigInt class can support both Decimal and Hexadecimal specialized template types. Also down the road if everything goes properly I'd also like to add the support to work with Complex numbers as well.

The BigInt class would be like this:

template<class NT>
BigInt {
private:
    Sign sign_;
    Digit<NT> carryDigit_;
    std::vector<Digit<NT>> value_;

    // May contain some functions such as setters and getters only
    // Do not want the class to be modifying itself except for assignment only.
};

And as above this would be specialized as well for Decimal and Hexadecimal Types, however if someone creates an instance of BigInt<> myBigInt this should default to Decimal!

For the data that is contained in the vector. I'd like to store the digits in reverse order of what one reads. So if their is a number 345698 in BigInt's internal vector it would be stored as 896543. The reason for this is when we do arithmetic operations in math we work from the least significant to the most significant starting at the right on the left side of the decimal point which is irrelevant since this is a BigInt only class and we work our way to the left. However if we store each digit that can only be 0-9 in each element of the above class's vector in the proper order and we use an outside operator+() function this would be challenging to do for one BigInt to another... example:

Basic Arithmetic R - L    | Vector storing standard
12345                       <1,2,3,4,5>
+ 678                       <6,7,8>
------  
13023

Here the indexes of <5> & <8> do not coincide so this makes it tough to figure out how to add a value with a few digits to one with many. My approach is that if we store the number in reverse order:

                         | Vector stored in reverse
                           <5,4,3,2,1>
                           <6,7,8>

Then the addition becomes simple! All we have to do is add each digit from both BigInt's vectors by same index value. And we have the use of the carry digit to carry over to the next field. The resulting BigInt would return with a size that is at least equal to or greater than the largest of the two BigInts. If the carryDigit has a value then the operation of addition on the next iteration will include 3 additions instead of two. Now when getting the BigInt for display we can return either a vector> except that when the user gets it this is not a "BigInt" it is vector of Digits and it is also in the correct order. It can even be returned by a string representation. This class can be constructed by a vector> and it will reverse the order when it stores it internally.

This is the overall concept of my BigInt class, I'm just wondering if this is a good design plan, if it would be considered efficient and I guess the main question that I have is about what to use to store the actual digits within the Digit's class... Would std::bitset<> be appropriate to conserve the memory foot print or would it just be better to use a char and not worry about the extra space with the pro of being simpler to implement?

Answer 1

-Update-

Okay I took some advise and this is what I have so far. I have not yet incorporated the concept of storing the values in reverse order which shouldn't be all too difficult. As it currently stands, I have eliminated all of the outside classes and my BigInt class signature looks like this:

class BigInt {
private:
    short sign_;
    uint32_t carry_{0};
    std::vector<uint32_t> value_;

public:
    BigInt() : sign_( 0 ) {}

    BigInt(  const uint32_t* value, const std::size_t arraySize, short sign = 0 ) : 
    sign_( sign ) {
        if( sign_ != 0 ) sign_ = -1;
        value_.insert( value_.end(), &value[0], &value[arraySize] );
        std::reverse( value_.begin(), value_.end() );
    }

    BigInt( const std::vector<uint32_t>& value, short sign = 0 ) : 
    sign_( sign ) {
        if( sign_ != 0 ) sign_ = -1;
        value_.insert( value_.end(), value.begin(), value.end() );
        std::reverse( value_.begin(), value_.end() );
    }

    BigInt( std::initializer_list<uint32_t> values, short sign = 0 ) : 
    sign_( sign ) {
        if( sign_ != 0  ) sign_ = -1;
        value_.insert( value_.end(), values.begin(), values.end() );
        std::reverse( value_.begin(), value_.end() );
    }

    std::vector<uint32_t> operator()() {
        //value_.push_back( static_cast<uint32_t>( sign_ ) ); // causes negative to be pushed into container multiple times...
        std::reverse( value_.begin(), value_.end() );
        return value_;
    }
};

I think this is a good start: there are several ways to construct one which gives the caller some flexibility since you can create a BigInt with a pointer, an array, a vector, or even an initializer list. At first it may seem counter intuitive to have the sign at the end of the constructor but I want to be able to have the sign value to be a defaulted parameter when the value is positive. If anything other than 0 is passed in for the sign value it will convert it to -1. A little more time and I'll have the signature of this class complete then I can move onto the operators that will work on it.

There are some minor pitfalls in the above code but I'm continuously working on them.

Answer 2

The smallest addressable unit of memory in C++ is a byte, and a byte is at least 8 bits (and usually exactly 8 bits). So your idea indeed wastes memory.

I also suspect you're not that familiar with math. What you call "NumberSystemType" is ordinarily called the base. So we talk about base-10 or base-16.

Now base-10 is only useful for human consumption, and thus pointless for this sort of bigints. Humans can't deal with numbers that have more than about 20 decimal digits anyway. So, pick a base that's useful for computers. And pick one. There's no need to support multiple bases. As paddy points out, base 2^32 is a perfectly reasonable base for computers.