3
\$\begingroup\$

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;
}
\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Compiling with optimization enabled should cause the function calls to be inlined. (clang does it at -O2.) \$\endgroup\$ – 200_success Dec 31 '13 at 20:31
  • 1
    \$\begingroup\$ 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 :) \$\endgroup\$ – ajay Dec 31 '13 at 22:08
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – 200_success Dec 31 '13 at 22:16
  • 2
    \$\begingroup\$ +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. \$\endgroup\$ – William Morris Jan 1 '14 at 1:00
  • \$\begingroup\$ @WilliamMorris Learned something new. Thanks! \$\endgroup\$ – 200_success Jan 1 '14 at 4:30

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.