6
\$\begingroup\$

I'm trying to calculate a problem which requires sum of digits in \$a^b\$, where \$0 \le a \le 9\$ and \$0 \le b \le 4000\$.

I have seen various other posts similar to this, but I haven't acquired best way. I have created this:

#include<stdio.h>
int main() {
    int digits[4000]={0} ;
    long long int test,a,b,temp,newVar ;
    scanf("%lld",&test) ;
    newVar=1 ;
    while(test--) {
        scanf("%lld %lld",&a,&b) ;
        if(b==0) {
            printf("Case %lld: 0\n",newVar) ;
            newVar++ ;
            continue ;
        }
        b=b-1 ;
        digits[0]=a ;
        long long int len=1,carry=0,i ;
        while(b--) {
            carry=0 ;
            for(i=0 ; i<len  ; i++) {
                temp=digits[i]*a + carry ;
                digits[i]=temp%10;
                carry=temp/10 ;
            }
            if(carry!=0) {
                digits[i]=carry ;
                len++ ;
            }
        }
        long long int sum=0 ;
        for(i=len-1 ; i>=0 ; i--)
            sum+=digits[i] ;
        printf("Case %lld: %llu\n",newVar,sum) ;
        newVar++ ;
    }
    return 0 ;
}

I tested my code for large powers, which is giving the right results.

For example:

Input:

3
2 32
3 2
2 60

Output:

Case 1: 58
Case 2: 9
Case 3: 82

Is there any way to increase the speed or running time of this code? I have a time limit of 1 sec and this code is showing Time Limit Exceeded.

This is not a contest that is going to effect my(or anyone else) ratings. For me, it's a way to learn new things. So any help will be appreciated.

\$\endgroup\$
  • 1
    \$\begingroup\$ There should be an easy maths way of calculating this using logs \$\endgroup\$ – Martin York Nov 17 '14 at 22:18
  • \$\begingroup\$ Is is safe to assume a ≥ 0 and b > 0? \$\endgroup\$ – 200_success Nov 18 '14 at 2:58
  • \$\begingroup\$ a>=0 and b>=0 is the specified condition along with upper bounds specified in question. \$\endgroup\$ – Prakhar Awasthi Nov 18 '14 at 7:57
  • \$\begingroup\$ @LokiAstari: Using logs you can give an approximation of a^b, but would that be good enough to sum all decimal digits? Do you have a hint or a concrete idea? \$\endgroup\$ – Martin R Nov 18 '14 at 8:23
6
\$\begingroup\$

In the comment to Martin R's answer there is a link to the question on Codechef. In the description they say that there can be at most 36000 test cases. I don't think that is coincidence because there are also 9 possible values for a and 4000+1 values for b.

Read the "at most 36000" as "probably that many", and caching comes to mind.

My solution is built on the cleaned up code from Martin R's answer but builds a look-up table first.

On some random input with 36000 entries, my code takes 0.334s while Martin R's code takes 21s. (About half of that time is taken by input/output from the command line.) The best solution on Codechef needs 0.03s but all other solutions are in that 0.3s range.

Code

#include <stdio.h>


const int A = 9; // 1 <= a <= 9
const int B = 4000+1; // 0 <= b <= 4000

const int BASE  = 100000000; // 10^8

/** fill a look up table with sums of digits for a^b, result is lut[a-1][b].
*/
void fillLUT(int lut[A][B]) {
for (int a = 1; a <= A; a++) {
    int digits[4000] = { 1 }; // TODO way larger than necessary
    int len = 1;
    for (int b = 0; b < B; b++) {
    // Write previous digits-sum into lut
    int sum = 0;
    for (int i = 0; i < len; i++) {
        int d = digits[i];
        while (d > 0) {
        sum += d % 10;
        d /= 10;
        }
    }
    lut[a-1][b] = sum;
    // Calculate next sum
    int carry = 0;
    for(int i = 0; i < len; ++i) {
        int temp = digits[i] * a + carry;
        digits[i] = temp % BASE;
        carry = temp / BASE;
    }
    if (carry != 0) {
        digits[len++] = carry;
    }
    }
}
}



int main() {
// Build Lookup-table.
int lut[A][B];
fillLUT(lut);

// Read input
int test, a, b;
scanf("%d", &test);
for (int i = 0; i < test; i++) {
    scanf("%d %d", &a, &b);
    if (a < 1 || a > A) {
    printf("Invalid input a:%d (b: %d)\n", a, b);
    return 1;
    }
    if (b < 0 || b >= B) {
    printf("Invalid input b:%d (a: %d)\n", b, a);
    return 2;
    }
    //int sum = powerDigitSum(a, b);
    int sum = lut[a-1][b];
    printf("Case %d: %d\n", i, sum) ;
}

return 0;
}
\$\endgroup\$
  • \$\begingroup\$ Creating lookUp table was the logic behind this question... Until today, I never looked that way for Codechef question, It's a cool new trick to have... Thanks for pointing out... \$\endgroup\$ – Prakhar Awasthi Nov 18 '14 at 16:07
  • \$\begingroup\$ @PrakharAwasthi also have a look at DarthGizka's answer. She/he uses Exponentiation by squaring and is faster than LUTs. (0.2s vs 0.3s) \$\endgroup\$ – Unapiedra Nov 18 '14 at 19:33
8
\$\begingroup\$

Some general remarks:

  • Use more and consistent spacing, e.g.

    digits[i]=temp%10;
    

    should be

    digits[i] = temp % 10;
    
  • Define variables only at the scope where they are used, e.g. carry is used only inside the while (b--) { ... } loop.

  • Move the actual computation to a separate function so that main() becomes shorter. That makes it also easier to add test cases.

  • Assuming that int has (at least) 32 bits (which is the case on all modern platforms), there is no need to use long long at all in your code.

  • There is no need to treat the case b = 0 separately. a ^ 0 is 1, and that can be covered with the general case if you start with digits[] = { 1 } instead of digits[] = { a }.

The performance can be increased by storing more than a single decimal digit in each array element digits[i]. Since 10^9 < 2^31, you can store 8 decimal digits in digits[i] and digits[i] * a + carry will still not overflow.

Your program would then look like this:

const int BASE = 100000000; //  10^8

int powerDigitSum(int a, int b) {
    int digits[4000] = { 1 } ;
    int len = 1;

    while (b-- > 0) {
        int carry = 0;
        for (int i = 0; i < len; i++) {
            int temp = digits[i] * a + carry;
            digits[i] = temp % BASE;
            carry = temp / BASE;
        }
        if (carry != 0) {
            digits[len++] = carry;
        }
    }

    int sum = 0;
    for (int i = 0; i < len; i++) {
        int d = digits[i];
        while (d > 0) {
            sum += d % 10;
            d /= 10;
        }
    }
    return sum;
}

int main() {
    int test, a, b;
    scanf("%d",&test) ;
    for (int i = 0; i < test; i++) {
        scanf("%d %d",&a,&b) ;
        int sum = powerDigitSum(a, b) ;
        printf("Case %d: %d\n", i, sum) ;
    }
    return 0 ;
}

Your original algorithm corresponds to BASE = 10. Using BASE = 100000000 instead reduced the computation time for a=9, b=4000 from 0.095 seconds to 0.014 seconds on my computer.

If that is not sufficient, you can use (unsigned) long long for the digits[] array and work with an even larger BASE.

\$\endgroup\$
  • 1
    \$\begingroup\$ Excellent posting! Another efficient optimisation is powering by repeated squaring, instead of doing b multiplications with a. You take a and start squaring, and whenever the corresponding bit is set in the exponent then you multiply the current power into the result. That cuts the number of required multiplications down to log_2(b) \$\endgroup\$ – DarthGizka Nov 17 '14 at 22:21
  • \$\begingroup\$ @DarthGizka: You are completely right, and I had thought about it. The above method was just easier to implement because it requires only a "big integer times small integer" multiplication, whereas repeated squaring requires the multiplication of two "big integers". \$\endgroup\$ – Martin R Nov 17 '14 at 22:27
  • \$\begingroup\$ I agree - your solution is much simpler than the method I suggested, and it is more than fast enough to beat the time limit. Hence it is the better solution. I only added my footnote as an additional treat for people studying your post, so to speak. As an avenue for even greater speed, at the cost of some complication. But in a sense continuing the thrust of the puzzle which is obviously designed to let people discover the basics of bigint math in an enjoyable way. \$\endgroup\$ – DarthGizka Nov 17 '14 at 22:32
  • \$\begingroup\$ It's a very good answer & I liked the way things became faster just by changing the base. But It is still not enough to beat the strict time limit of the problem (maybe because of large number of test cases). I'll love to see other ways too... \$\endgroup\$ – Prakhar Awasthi Nov 18 '14 at 8:17
  • 1
    \$\begingroup\$ @Unapiedra: Sure. The result has at most 4000 decimal digits, and each array element holds 8 of them, so digits[500] would be sufficient. – Great answer, btw.! \$\endgroup\$ – Martin R Nov 18 '14 at 19:43
4
\$\begingroup\$

In case Martin R's excellent solution should not be fast enough: there is a trick that can drastically reduce the number of multiplications needed for raising a number to the nth power. Instead of doing (n - 1) multiplications with x, you do only a small number of repeated squarings and multiplications.

The basic idea is easily demonstrated:

$$x^4 = x * x * x * x = (x^2)^2$$

Or, as a more drastic example:

$$x^{16} = x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x = (((x^2)^2)^2)^2$$

Exponents that are not a power of two can also be handled efficiently:

$$x^5 = (x^2)^2 * x$$

How to decide which squaring of x to multiply into the result and which not? Easy: if the binary representation of the exponent has bit i set, then the ith squaring of x needs to be multiplied into the result. Although this is not a very mathematical way of putting things, it happens to be very practical.

The principles can be explored by using a builtin type as a stand-in for a big integer:

typedef uint64_t bigint_t;

bigint_t nth_power (bigint_t x, unsigned exponent)
{
   bigint_t result = 1;

   for ( ; exponent; exponent >>= 1)
   {
      if (exponent & 1)
      {
         result *= x;
      }

      x *= x;
   }

   return result;
}

This requires k squarings for an exponent where the most significant bit is k, and as many multiplications into the result as there are '1' bits in the exponent:$$x^{1025}$$ requires only ten squarings and two separate multiplications, instead of 1024 for simple repeated multiplication.

A few more multiplications can he shaved off by handling beginning and end more efficiently, but that is an uglifying optimisation that obscures the basic idea. A tiny bit more speed, but the code gets more complicated and less readable. Don't uglify your code unless you have incontrovertible proof that you have to.

Here's a simple demo implementation of this algorithm that uses std::vector<> as a faux big integer:

typedef std::vector<uint32_t> fake_bigint;

fake_bigint &nth_power (fake_bigint &result, uint32_t base, unsigned exponent)
{
   fake_bigint current_power(1, base);

   result.resize(1);
   result[0] = exponent & 1 ? base : 1;

   while (exponent >>= 1)
   {
      current_power *= current_power;

      if (exponent & 1)
      {
         result *= current_power;
      }
   }

   return result;
}

Almost exactly the same as simple version that used big integers... That's why I like C++.

Here's the implementation for operator *=:

void operator *= (fake_bigint &multiplicand, fake_bigint const &multiplier)
{
   fake_bigint result(multiplicand.size() * 2);

   for (unsigned n = unsigned(multiplier.size()), i = 0; i < n; ++i)
   {
      addmul_1(result, i, multiplicand, multiplier[i]);
   }

   while (result.size() > 1 && result.back() == 0)
   {
      result.pop_back();
   }

   multiplicand.swap(result);
}

The real meat is in the addmul_1 helper function that multiplies a big integer by a single word and adds the product to a big integer, at a certain offset from its lower end to reflect the implied power of two for the multiplicand.

void addmul_1 (fake_bigint &result, unsigned offset, fake_bigint const &multiplicand, fake_bigint::value_type multiplier)
{
   result.resize(std::max(result.size(), offset + multiplicand.size()));

   uint64_t accu = 0;

   for (fake_bigint::size_type n = multiplicand.size(), i = 0; i < n; ++i)
   {
      accu += result[offset + i] + uint64_t(multiplicand[i]) * multiplier;
      result[offset + i] = uint32_t(accu);
      accu >>= 32;
   }

   for (fake_bigint::size_type k = offset + multiplicand.size(); accu; ++k)
   {
      if (k < result.size())
         result[k] = uint32_t(accu += result[k]);
      else
         result.push_back(uint32_t(accu));
      accu >>= 32;
   }
}

On my laptop this computes 9999^9999 in 6.4 ms; I put the number in my pastebin (39996 digits).

\$\endgroup\$
  • \$\begingroup\$ Generally a very good approach, except that in this case almost all a^b (for all b) are required. Thus your approach needs O(b log b) while mine (LUT) has O(b). \$\endgroup\$ – Unapiedra Nov 18 '14 at 16:57
  • \$\begingroup\$ My simplistic demo implementation of this algorithm takes 6.4 ms to compute 9999^9999, and 0.2 ms for 9^4000. Output verified against gp/PARI. Time limits shouldn't pose too much of a difficulty here... \$\endgroup\$ – DarthGizka Nov 18 '14 at 19:11
  • \$\begingroup\$ I just measured this: You are right. Your version takes 0.2s and the LUT takes 0.3s (for the same set of inputs, 36000 entries). EDIT: I used your previous edit as a basis. \$\endgroup\$ – Unapiedra Nov 18 '14 at 19:31
3
\$\begingroup\$

Simple method extraction will help a lot with your code. Additionally, you create a number of variables that are unreasonably large... why do you need long long values?

The conditions for the program are clear, that the input cases will be relatively few, and that the base and power are small too (the base is <= 10, and the power is <= 4000).

Notice how you can allocate the digits array inside the method call, and that there's no need to over-allocate the array. This makes the methods reusable and re-entrant. The main method handles the user interaction, and the rest of the logic is extracted in to self-standing calls.

I have used simple int variables because there's no need for more precision on the basic digits, carry, or inputs. The only place where more precision is needed is for the sum, where, with some unlikely power that has 4000 digits of 9, will sum to 36000, which is larger than can fit in a signed 16-bit value, but unsigned is fine. On further reflection, the largest power will be significantly less than 4000 digits, at most \$9^{4000}\$ which will be about 3600 digits in total, with at worst case all being 9's (they are not), will be less than 32768. So, a signed int will be fine for the sum too.

All up, the code can be simplified as:

#include<stdio.h>

int multiply (int *digits, const int len, const int mult) {
    int carry = 0;
    for (int i = 0; i < len; i++) {
        digits[i] *= mult;
        digits[i] += carry;
        carry = digits[i] / 10;
        digits[i] %= 10;
    }
    if (carry) {
        digits[len] = carry;
        return len + 1;
    }
    return len;
}

unsigned int sumPower(const int base, const int power) {
    int digits[power + 1];
    digits[0] = 1;
    int len = 1;
    for (int i = 1; i <= power; i++) {
        len = multiply(digits, len, base);
    }
    unsigned int sum = 0;
    while (--len >= 0) {
        sum += digits[len];
    }
    return sum;
}

int main() {
    int tests,a,b,newVar ;
    scanf("%d",&tests) ;
    newVar=1 ;
    while(tests--) {
        scanf("%d %d",&a,&b) ;
        printf("Case %d: %d to %d -> %u\n", newVar, a, b, sumPower(a, b)) ;
        newVar++ ;
    }
    return 0 ;
}
\$\endgroup\$
  • \$\begingroup\$ "Simple method extraction will help a lot with your code" will it lead to performance gain? I don't think so. It only make code more readable which doesn't matter much in coding contests. However, good coding practice should be always promoted. \$\endgroup\$ – Kunal Krishna Nov 18 '14 at 10:42
  • 2
    \$\begingroup\$ @KunalKrishna - You suggest method extraction will slow things down, but have you tested it? In general, method extraction not only improves readability, but the compiler is quite capable of inlining the method, and there's no performance loss. \$\endgroup\$ – rolfl Nov 18 '14 at 12:04
  • \$\begingroup\$ "You suggest method extraction will slow things down".I never said that. I just thought mere code re-factoring won't improve performance for it's complexity still remains the same. \$\endgroup\$ – Kunal Krishna Nov 19 '14 at 5:18

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.