5
\$\begingroup\$

I have a bottleneck in my program at the point where I calculate the digit sum and product of a number. I am using GMP because I have to work with numbers that follow \$1e8 < n < 1e80\$.

To calculate the sum/product of a number, I initially used strings, thinking the division/modulo method would result in an improvement later on.

However, when I later implemented this it turned out that this did not give me a performance improvement.

mpz_class num = 1120390317;
mpz_class sum = 0;
mpz_class pro = 1;

while(num != 0) {
    mpz_class rem = (num % 10);
    sum += rem;
    pro *= rem;
    num = num / 10;
}

Instead of:

mpz_class num = 1120390317;
mpz_class sum = 0;
mpz_class pro = 1;

const std::string strNum = num.get_str();
for (auto c : strNum) {
    int res = c - '0';
    sum += res;
    pro *= res;
}

In the actual program the values of num are actually in the before mentioned range. But they provide results about equal to this test case.

The test case and the program shows me (with or without optimizations) using the first method is 3x as slow. How can I improve the modulo version to run faster than the string version? Or should I use the string version? If so, can that be optimized?

\$\endgroup\$
4
\$\begingroup\$

There are a few ways to speed up your division. First, note that because rem is declared within the while loop, it's both constructed and destroyed every loop iteration. That's not really necessary, so you could instead declare it outside the loop and simply assign a new value within the loop each time. Also by changing the line from num = num / 10 to num /= 10, you avoid creating and destroying yet another temporary. Applying both of those saves a little time, but it's still slower than the string method because you're essentially performing the division twice (once for num % 10 and again for num / 10).

The key is to do only a single division per loop, but you'll have to resort to using the underlying C function since it's not exposed to the C++ interface. Fortunately, it's simple to do so:

unsigned long digit;
while(num != 0) {
    digit = mpz_tdiv_q_ui(num.get_mpz_t(), num.get_mpz_t(), 10);
    sum += digit;
    pro *= digit;
}

On my machine this is slightly faster than the string method, and probably uses a little less memory.

Update:

Because the speed of that code relative to the string method varies based on what compiler optimizations are used, it's not necessarily always faster. This version uses low-level GMP calls for more speed:

__mpz_struct *q = num.get_mpz_t();
while(*(q->_mp_d) != 0) {
    auto digit = mpn_divrem_1 (q->_mp_d, (mp_size_t) 0, 
            q->_mp_d, q->_mp_size, (mp_limb_t) 10);
    sum += digit;
    pro *= digit;
}

This makes a couple of assumptions that are important. First, it assumes that num > 0 and it dives deep into the internal structure of __mpz_struct so it will not be very durable to changes in GMP, should they decide to change the underlying representation of numbers. However, with this code, I find that it's a bit faster on my machine than the string method, both with and without -O3 optimizations.

Also, note that within your range of integers, the sum of digits will always fit within a long int which will save time, but could equally be applied to the string method.

\$\endgroup\$
  • \$\begingroup\$ Something like this? It's still not as fast although a bit closer, am I missing something? \$\endgroup\$ – Floris Velleman May 31 '14 at 19:34
  • \$\begingroup\$ @FlorisVelleman It's all in how you compile it. Without the -O3 flag, on my machine, this version is faster, but with it, the string version is faster. You may be able to use the mpn_tdiv_qr() function to further optimize, but you'll also have to write more code since that's a low-level function. \$\endgroup\$ – Edward May 31 '14 at 21:09
  • \$\begingroup\$ Tested a bit with the flags but I don't seem to be able to get equal or better results. Do you think the low level functions will cover the gap (perhaps even faster timings)? \$\endgroup\$ – Floris Velleman May 31 '14 at 22:05
  • \$\begingroup\$ It is running at about the same speed on my machine now. Switching sum to long really helped out. Thanks! \$\endgroup\$ – Floris Velleman Jun 1 '14 at 15:25
  • 1
    \$\begingroup\$ For a very large number (e.g., a number with 10e8 digits), the string method is the fastest, as I have done in this Code Challenge. \$\endgroup\$ – justhalf Sep 5 '14 at 7:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.