Sum of digits in a^b

Question

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.

Answer 1

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;
}

Answer 2

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.

Answer 3

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).

Answer 4

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 ;
}