Project Euler #16 - C

Question:

2¹⁵ = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.
What is the sum of the digits of the number 2¹⁰⁰⁰?

Solution:
I'm sure many beginning programmers get stumped on this one. "I used the pow function but I just cant get the right answer." Well, the problem is a that 2^1000 wont fit in a 2^32 word. So, I will use a method I have used for a couple of previous PE problems... it is something that may be a bit advanced for some of you: multiplication and addition.

The way to go about this is to imagine these numbers as one huge number, but rather as an array of digits between 0 and 9. Then, proceed like you were taught in elementary school... multiply -> carry -> multiply -> add -> carry... and repeat. Example:

    19
x   3


First, 3 x 9 = 27. We bring the 7 down, carry the 2. Then, 3 x 1 = 3 + 2 (carry) = 5. So, 3 x 19 = 57.

This is the exact process used to solve this problem. First, create an empty array and set the first element to 1 (digits[0] = 1). We will want to multiply successive products by 2.
2 x 2 = 4
2 x 4 = 8
2 x 8 = 16
etc. But rather than saving as an individual product, you save the digits in the array.

This requires two loops: an outer loop that loops from 1 - 1000, and an inner loop which multiplies each individual member of the array by 2 using the process described above.

Upon completion of the outer loop, the array should contain the number 2^1000.
Simply sum the digits, and you are done.
Here is the C code. I use a placeholder of the highest use index to reduce the number of loop iterations but it is optional.

#include <stdio.h>
#define SIZE  500
#define POWER  1000


int main (void)
{
int digits[SIZE] = {0};
int high_order = 0;
int i = 1;
int sum = 0;


/* 
Could start from the maximum 64 bit integer to save 
some calculations but I do not do so here.
*/


digits[0] = 1;


for (i = 1; i <= POWER; i++)
{
int j;
int carry = 0;
int product = 1;


for (j = 0;  j <= high_order; j++)
{
product = (digits[j] << 1) + carry; 
digits[j] = product % 10;
carry = product / 10; 


if ( ( carry != 0 ) && ( j == high_order ) )
high_order++;
}
}


for (i = 0; i <= high_order; i++)
sum += digits[i];


printf("Sum is %d\n", sum);
return 1;
}