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 &lt;&lt; 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 &amp;string_input, std::string &amp;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 &gt;= 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 &gt;= 1) buffer[n++] = (char)('0' + t_1);
    if(n) string_tmp.append(buffer, n);
}


void BigInteger::incrementNumberString_1A63(std::string &amp;string_input, std::string &amp;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 &lt; 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 &gt;= 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 &amp;os) const
{
    const BigInteger &amp;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) // --&gt; Access each bit
        for(i = num_sz - 1; i &gt;= 0; i--)
        {
            doubleNumberString_1A63(buf_base10, buf_basetmp);
            incrementNumberString_1A63(buf_base10, buf_basetmp, BigInteger::IntegerUnit::toDigit(num.operator[](i)));
        }

        os &lt;&lt; buf_base10;
    }   
}


std::ostream &amp;operator &lt;&lt; (std::ostream &amp;os, const BigInteger &amp;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.
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 &lt;&lt; static_cast&lt;int&gt;(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.