CODEWITHSUNDEEP
c++performanceoptimizationbiginteger
ampawd
ampawd

Reputation: 1010

Efficient way of allocating memory for big unsigned integer

I wrote a C++ class for big unsigned integer containing up to 10^5 decimal digits, it has got a BASE = 10^9 and std::vector<long long> inside to store actual number -

for example 754564575693573452 is stored as

std::vector<long long> number = {693573452, 754564575}

In the constructor I resize this vector to always contain some fixed number of long long digits, lets say its 10^5, therefore a single addition of two big uints can have up to a 10^6 digits (which is 9 * 10^6 digits in BASE = 10^1 numeral system), and similarly for multiplication...

So there's a 9 times speed up for all arithmetic operations but this is noticed only for a few calculations on big numbers, for a cases with a lot of computations the performance slows down, and this is because of the class design, my constructor and default constructor always call resize function as I said before, which is linear time routine.

void Big_uint::read_num_str(const std::string& num_str)
{
    // reading from num_str to number
}

Big_uint::Big_uint(const std::string& num_str = "0")
{
    number.resize( 1000000 );
    read_num_str(num_str);  
}

Big_uint::Big_uint(const long long& num)
{
    number.resize( 1000000 );
    char buff[ 20 ];
    _itoa_s(static_cast<int>(num), buff, 10);
    std::string s = buff;
    read_num_str(s);    
}

and all the arithmetic operations are implemented in this way

Big_uint operator + (const Big_uint& left, const Big_uint& right)
{
    Big_uint res; // resize() called here to initialize a vector
    // add algorithm
    return res; 
}

Big_uint operator * (const Big_uint& left, const Big_uint& right)
{
    Big_uint res; // resize() called here to initialize a vector

    // some multiplication algorithm here (currently only naive O(n^2) implemented)

    return res; 
}

Thus, they become inefficient.

How can I have the vector be already initialized depending on the input in operator overloads ?

I dont wan't to change operator overloads to a member functions like add, mul, div and pass them 3 parameters, where 3rd one would be a res - a preallocated zero initialized Big_uint to store the result of binary operation.

Upvotes: 1

Views: 293

Answers (1)

geza
geza

Reputation: 29970

You shouldn't preallocate storage this way. Don't preallocate at all. At every operation, you know (approximately) the size of the result. For add, it is the maximum of the inputs' size plus one. For mul, it is the sum of the inputs' size. Always try to allocate only the necessary space to hold the number.

So, the default constructor shouldn't allocate at all. Every other constructor should check the size of the input, and allocate the necessary space. Operators should (conservatively) approximate the necessary space, and allocate accordingly.

A side note: you should use base 2^32 instead of 10^9 (or 2^64 on a 64-bit machine): it has slightly less memory consumption, and performance will be much better.

Side note 2: sizeof(long long) is usually 8, so you waste memory if you only store numbers less than 10^9 in it.

Upvotes: 3

Related Questions