Calculating the sum of the digits in 2^1000

Question

I have a program which calculates the sum of the digits in the number 2¹⁰⁰⁰. The program is not beautiful and I was hoping for some advice on how to improve it.

The idea I have used is to create an array with the first element equal to 2⁰. The first element in the array represent 10⁰ the second 10¹ and so on. Then go through and double every element in the array. After every element is doubled I check if an element in the array is greater than 9, if it is I subtract 10 and add a 1 to the next element in the array. For example if the element at place 40 is equal to 13 and element at place 41 is equal to 3 then I will change the element at place 40 to 3 and element at place 41 to 4.

#include <stdio.h>
int main(void){
 int sum = 0;
 int dec[320] = {1, };
 int i,j,p,q;
 for(i = 1; i < 1001; i++){
 for (j = 0; j < 302; j++) {
 dec[j] = 2*dec[j];
 }
 for(q = 0; q < 302; q++){
 if(dec[q] > 9){
 dec[q] = dec[q] % 10;
 dec[q+1] = dec[q+1] + 1;
 }
 }
 }
 for(p = 0; p < 302; p++){
 sum += dec[p];
 }
 printf("sum = %d sista %d \n", sum, dec[301]);
}

• DarthGizka: Note: if you are looking for more speed then you could try an alternative approach: make an array that as 1000 bits 0 (i.e. 125 x byte 0) and a single lone bit 1 at the end (or more realistically an array with 32 uint32_t where the high word is 0x100). Then pretend it's a bignum, convert to decimal, and sum the digits... If you pretend that one 'digit' is actually 9 decimal digits long (or 18, for uint64_t) then you get away with 36 or 18 long divisions respectively, and you can use the C runtime for converting the 'meta-digits'.

Answer 1

I see some things that may help you improve your code.

Eliminate "magic numbers"

The code, is full of "magic numbers" -- that is, raw numbers in the code that don't have obvious meaning. For example, we have this:

int dec[320] = {1, };
// and later ...
for (j = 0; j < 302; j++) {

It's unclear, whether 302 and 320 is just a typo or has some signficance. Better would be to use a #define for this. I'd use this:

#define BITS 1000
#define DIGITS 302

Write in idiomatic C

Lines like these are a little peculiar to an experienced C programmer:

dec[q] = dec[q] % 10;
dec[q + 1] = dec[q + 1] + 1;

The idiom instead would be to write them like this:

dec[q] %= 10;
++dec[q + 1];

Avoid potentially expensive operations

Since you're only doubling each digit each pass, it's certain that the maximum possible value is 9*2 = 18, so rather than using the % operator, it's sufficient to simply subtract 10.

Make only a single pass through

There's no need to make two passes through the array for each doubling. It can be done in a single pass like this:

for (int i = BITS; i; --i) {
 int carry = 0;
 for (int j = 0; j < DIGITS; j++) {
 dec[j] = 2 * dec[j] + carry;
 if (dec[j] > 9) {
 dec[j] -= 10;
 carry = 1;
 } else {
 carry = 0;
 }
 }

• chux: Minor: In keeping with the spirit of no/minimizing magic numbers, if (dec[j] > 9) { --> if (dec[j] >= 10) {

Answer 2

Don't hardcode the which power of 2 we want to calculate. We'll want to use some smaller values to be sure we get reasonable results we can compute by hand:

int sum_power_digits(int power);

And let's write a main() that can run it as many times as we need, passing values as program arguments:

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char **argv)
{
 while (*++argv) {
 char *e;
 long l = strtol(*argv, &e, 10);
 if (*e || l < 0 || l > INT_MAX) {
 fprintf(stderr, "%s: not valid\n", *argv);
 continue;
 }
 int result = sum_power_digits((int)l);
 if (!result) {
 fprintf(stderr, "%s: FAILED\n", *argv);
 continue;
 }
 printf("sum_digits(2^%s) = %d\n", *argv, result);
 }
}

I have made the interface decision that a return value of 0 indicates an error; we could use negative numbers to signal different kinds of error.

---

Okay, let's move on to the implementation. We can no longer assume a fixed size array to store the digits, so we must allocate what's required. I'm going to save on storage compared to your algorithm, by storing two digits in each element, at the cost of a little more complexity. I'm further saving on storage, as uint8_t is usually smaller than int.

#include <stdint.h>
int sum_power_digits(int power)
{
 /* We count in base 100; our character type needs to hold up to 198 */
 typedef uint8_t digit;
 int digits = power / 6 + 1; /* safe upper bound */
 digit *d = calloc(digits, sizeof *d);
 if (!d) {
 fprintf(stderr, "%d: failed to allocate memory\n", power);
 return 0;
 }
 *d = 1; /* start with 2^0 */
 int carry = 0;
 digit *end = d + digits;
 while (power-->0) {
 for (digit *p = d; p < end; ++p) {
 *p *= 2;
 *p += carry;
 carry = *p/100;
 *p %= 100;
 }
 }
 /* count the decimal digits */
 int sum = 0;
 for (digit *p = d; p < end; ++p)
 sum += *p % 10 + *p / 10;
 free(d);
 return sum;
}

Notice that I typedeffed the digit type - this worked in my favour when I realised it need to represent up to 198 (needed when doubling 99), and my original choice of char (which could be signed) might only reach 127.

---

Remember what I said about testing? Let's have a go:

$ ./126981 1b a -1
1b: not valid
a: not valid
-1: not valid
$ ./126981 `seq 0 9` 1000 2000 262144
sum_digits(2^0) = 1
sum_digits(2^1) = 2
sum_digits(2^2) = 4
sum_digits(2^3) = 8
sum_digits(2^4) = 7
sum_digits(2^5) = 5
sum_digits(2^6) = 10
sum_digits(2^7) = 11
sum_digits(2^8) = 13
sum_digits(2^9) = 8
sum_digits(2^1000) = 1366
sum_digits(2^2000) = 2704
sum_digits(2^262144) = 353041

I'm pretty confident of the single-digit results (that I can do in my head), so I have some faith in the big result. Once we got to 2^7, we demonstrated that carry is working (finally, 2^9 = 512; 5+1+2 = 8).

• chux: digit *end = d + digits; should occur after if (!d) {...}
• chux: How is this true: "unsigned char wasn't portable enough to represent up to 198"? If uint8_t works, certainly unsigned char works.
• Toby Speight: @chux, thanks for the correction. And you're right about unsigned char - I mistakenly thought that CHAR_BIT could be 7, (giving 5 chars in 36-bit hardware), but it actually must be 8 or more. I did originally use char, forgetting it needed to briefly represent values more than 99. That's a definite bug, and I did fix that before posting.