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.

Of course it is heavily optimized. How about you write a quick class definition for yourself, particularly paying attention to the operator [] which can either return 0 or 1. Of course, the container is a std::vector. — user116913, Sep 27 '16 at 11:26
Posting at least the class definition - the implementation is 2503 lines long. — user116913, Sep 27 '16 at 11:27
My BigInteger class stores its values in real bits (OR 32 bits per container element). The container element is an uint32_t. — user116913, Sep 27 '16 at 11:30

user4407569 · Accepted Answer · 2016-09-27 12:20:28Z

2

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.

edited Sep 27 '16 at 12:20

answered Sep 27 '16 at 11:46

user4407569

5612 silver badges8 bronze badges

\$\begingroup\$ '_1A63' : Random postfix to make the functions sound unique. It says that the functions are probably reversed for private program implementation. \$\endgroup\$ – user116913 Sep 27 '16 at 12:41
\$\begingroup\$ I will try your suggestion. If everything works out, I guarantee your answer will be accepted :) \$\endgroup\$ – user116913 Sep 27 '16 at 12:42
\$\begingroup\$ @xersi Implementation methods are simply declared private in C++, so there is no way for others to use them. There is also no naming conflict, because the author of the class is the only one able to declare member functions. Even for derived types that is not a problem. \$\endgroup\$ – user4407569 Sep 27 '16 at 12:55
\$\begingroup\$ Help!! The Double dabble algorithm is not working!! \$\endgroup\$ – user116913 Sep 27 '16 at 14:45
1

\$\begingroup\$ arr = {0, 0, 1} // == 2^64, no, the first element of arr has the highest significance. It is good practise to adhere to the standard even if recent x86 desktop platforms usually have int as 32bit. Think of someone trying to compile your code for some small microcontroller. I am not here to write your code for you. You should worry about your code. You should even implement the algorithm yourself instead of copying it from wikipedia. What is the point if you don't understand the code? \$\endgroup\$ – user4407569 Sep 27 '16 at 16:39

| show 10 more comments

user116913 · Accepted Answer · 2016-09-28 01:25:11Z

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.

Stack Exchange Network

current community

your communities

more stack exchange communities

Converting bits to decimal (integer) string is so slow

2 Answers 2

Your Answer

Hot Network Questions

Converting bits to decimal (integer) string is so slow

2 Answers 2

Your Answer

Sign up or log in

Post as a guest

Related

Hot Network Questions