Converting bits to decimal (integer) string is so slow

Question

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.

Answer 1

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 << static_cast<int>(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.

Answer 2

I am glad I am able to solve this problem thanks to Eichhörnchen. Everything works out, and as a plus, I even managed to increase my raw calculation performance up to 36.96%!!

Before :

• 2 ^ 200000 == Time Elapsed : 12.343

• Number of binary digits : 200001

• Printing foo took 160.485 second(s)

After :

• 2 ^ 200000 == Time Elapsed : 7.781

• Number of binary digit : 200001

• Printing foo took 20.672 second(s)

That is at least 8x faster. Even though it is not that extremely impressive, I can now believe that implementing a BigInteger is not that very challenging and very difficult anymore. Sure it may be great if there is an even more impressive algorithm out there, I will get to discover it soon if there's any.