I am implementing myself a BigInteger class. It can natively handle very very big digits in very short time.
2 ^ 200000 == Time Elapsed : 12.343
Number of binary digits : 200001
The only problem is, when I do std::cout << foo;
, I have to wait for very very long. Because my BigInteger class has to perform a std::string multiplication and a std::string increment on very single bit. As the number of bits increases, it might even take ages to finish.
Printing foo took 160.485 second(s) // It is so so long!!!
I have actually optimized my outputting algorithm to the best of my abilities. Some tricks include using reference, using array temp variables for fast caching. But for very very big numbers, it is still not fast enough.
Here is my code :
void BigInteger::doubleNumberString_1A63(std::string &string_input, std::string &string_tmp)
{
int64_t i;
int32_t t, t_1 = 0, t_2;
string_tmp = "";
char buffer[1024];
int32_t n = 0;
for(i = string_input.size() - 1; i >= 0; i--)
{
t = t_1 + (string_input[i] - '0') * 2;
t_1 = t / 10;
t_2 = t % 10;
buffer[n++] = (char)('0' + t_2);
if(n == sizeof(buffer)){string_tmp.append(buffer, n); n = 0;}
}
if(t_1 >= 1) buffer[n++] = (char)('0' + t_1);
if(n) string_tmp.append(buffer, n);
}
void BigInteger::incrementNumberString_1A63(std::string &string_input, std::string &string_tmp, int32_t inc_val = 1)
{
int64_t i;
int32_t t, t_1 = 0, t_2;
string_input = "";
char buffer[1024];
int32_t n = 0;
for(i = 0; i < string_tmp.size(); i++)
{
t = t_1 + (string_tmp[i] - '0') + inc_val;
t_1 = t / 10;
t_2 = t % 10;
inc_val = 0;
buffer[n++] = (char)('0' + t_2);
if(n == sizeof(buffer)){string_input.append(buffer, n); n = 0;}
}
if(t_1 >= 1) buffer[n++] = (char)('0' + t_1);
if(n) string_input.append(buffer, n);
std::reverse(string_input.begin(), string_input.end());
}
void BigInteger::printRawBinaryToDecimal(std::ostream &os) const
{
const BigInteger &num = (*this);
int64_t i;
int64_t num_sz = num.size();
if(BIG_INTEGER_INTEGER_DIGIT_BASE_A8F23ABC == 2)
{
std::string buf_base10 = "0";
std::string buf_basetmp;
// num.operator[](i) // --> Access each bit
for(i = num_sz - 1; i >= 0; i--)
{
doubleNumberString_1A63(buf_base10, buf_basetmp);
incrementNumberString_1A63(buf_base10, buf_basetmp, BigInteger::IntegerUnit::toDigit(num.operator[](i)));
}
os << buf_base10;
}
}
std::ostream &operator << (std::ostream &os, const BigInteger &num)
{
num.printRawBinaryToDecimal(os); return os;
}
Here we go, for each bit, the BigInteger class has to call doubleNumberString_1A63 and incrementNumberString_1A63, and it is the traditional method (and slow of course). Could anyone greatly improve it or suggest even a faster algorithm? I would really appreciate it.