# Function to find sum of digits in the number a^b where a, b are positive integers

I was solving Project Euler problem 16, which asks to find the sum of digits of the number 2 raised to the power 1000. Using Python, it can be solved in one line of code:

sum(map(int, list(str(2**1000))))


It felt too easy so I decided to write a function in C to do the same job. Here's my program. In what ways can I improve it? Please suggest good practices also.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <assert.h>

int sumdigit(int a, int b);

int main(void) {
int a = 2;
int b = 10000;
printf("%d\n", sumdigit(a, b));
return 0;
}

int sumdigit(int a, int b) {
// numlen = number of digit in a^b
// pcount = power of 'a' after ith iteration
// dcount = number of digit in a^(pcount)

int numlen = (int) (b * log10(a)) + 1;
char *arr = calloc(numlen, sizeof *arr);
int pcount = 0;
int dcount = 1;
arr[numlen - 1] = 1;
int i, sum, carry;

while(pcount < b) {
pcount += 1;

sum = 0;
carry = 0;

for(i = numlen - 1; i >= numlen - dcount; --i) {
sum = arr[i] * a + carry;
carry = sum / 10;
arr[i] = sum % 10;
}

while(carry > 0) {
dcount += 1;
sum = arr[numlen - dcount] + carry;
carry = sum / 10;
arr[numlen - dcount] = sum % 10;
}
}

int result = 0;
for(i = numlen - dcount; i < numlen; ++i)
result += arr[i];

free(arr);
return result;
}


The problem calls for computing the sum of digits in 21000. You did 210000. Overachiever!

There are a few things you could do to improve readability.

char *arr looks a lot like a string. One might initially think that you are storing the number as a string (i.e., ASCII '0''9'). You could dispel that impression by changing it to unsigned char *arr. To be even clearer, I would use a typedef unsigned char digit; so that you can declare digit *arr. Then it is clear that you are using binary-coded decimal.

As long as you are doing binary-coded decimal, there is no advantage to putting the most-significant digit first. With the least-significant digit first, the code is simpler, and there is the nice property that the number is sum(arr[i] * 10**i for i in range(len(arr))).

For further readability, I would define a struct to represent the big decimal:

typedef unsigned char digit;

typedef struct {
int capacity;
int dcount;
digit *digits;  /* Unsigned binary-coded decimal. The number is
sum(arr[i] * 10**i for i in range(dcount)) */
} bigdecimal;


There are a lot of variables in your sumdigit() — not quite a mess, but enough to start being concerned. The function name sumdigit is also a bad code smell. I would also decompose the operations for readability. (Defining the bigdecimal type makes that practical.)

void mult(unsigned int a, bigdecimal *b) {
int carry = 0;

for (int i = 0; i < b->dcount; ++i) {
int sum = a * b->digits[i] + carry;
carry = sum / 10;
b->digits[i] = sum % 10;
}

while (carry > 0) {
int sum = b->digits[b->dcount] + carry;
carry = sum / 10;
b->digits[b->dcount] = sum % 10;
b->dcount++;
}
}

bigdecimal *exponentiate(unsigned int base, unsigned int power) {
bigdecimal *result = malloc(sizeof(bigdecimal));
result->capacity = 1 + (int) (power * log10(base));
result->digits = calloc(result->capacity, sizeof(digit));

/* base**0 == 1 */
result->digits[0] = 1;
result->dcount = 1;

for (int p = 0; p < power; p++) {
mult(base, result);
}

return result;
}

unsigned int sumdigit(bigdecimal *b) {
unsigned int sum = 0;
for (int i = b->dcount - 1; i >= 0; --i) {
sum += b->digits[i];
}
return sum;
}

void free_bigdecimal(bigdecimal *b) {
free(b->digits);
free(b);
}

int main(void) {
bigdecimal *n = exponentiate(2, 1000);
printf("%u\n", sumdigit(n));
free_bigdecimal(n);
return 0;
}


I've used C99 variable scoping in the for-loops because it's nicer.

• Compiling with optimization enabled should cause the function calls to be inlined. (clang does it at -O2.) – 200_success Dec 31 '13 at 20:31
• In the function sumdigit, wouldn't iterating the for loop from i = 0 to i = b->dcount - 1 be simpler? Thanks a lot for many ideas on how to form abstractions and write clean, readable code :) – ajay Dec 31 '13 at 22:08
• A for-loop counting up is more conventional. A for-loop counting down to 0 is a micro-optimization: CPUs have special instructions for comparing numbers with 0. The difference in performance would be negligible, so either way would be fine. – 200_success Dec 31 '13 at 22:16
• +1. I'd be inclined to save one allocation by passing the bigdecimal pointer into exponentiate so that the caller can define it on the stack. Either that or make the digits pointer a zero dimension array and allocate the struct in a single calloc. Also sumdigit should have a const parameter. – William Morris Jan 1 '14 at 1:00
• @WilliamMorris Learned something new. Thanks! – 200_success Jan 1 '14 at 4:30