Converting bits to decimal (integer) string is so slow

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 = 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::s

You are trying to do arithmetic with strings, that is bound to be expensive.

Here is a naive algorithm to output a BigInteger in decimal:

std::stringstream output;
BigInteger num = the_number;
while(num != 0) {
    output (num%10);
    num = num/10;
}
std::string output_str = output.str();
std::reverse(output_str.begin(), output_str.end());
return output_str;

of course you need to implement the operators %, / and cast to int first.

This can also be easily improved by chunking to the maximal power of 10 holdable in an unsigned int or unsigned long.

However this naive algortithm still has quadratic time complexity in the length of the number. I am not sure whether there is a linear time algorithm. Another quadratic, but possibly faster algorithm is Double dabble.

In the GMP documentation there is a short explanation of a subquadratic algorithm. Maybe this can give you some directions. You may want to look at its source anyway as a reference of a mature BigInteger implementation.

I am also quite confused by your function names. What is _1A63 supposed to mean? I doubt the end of the function name is the correct place for whatever it is. Is it representing the container element types? If so that should belong into a template parameter.

StackExchange Code Review Q#142588, answer score: 2