Adding Large Numbers in C
As an interesting coding exercise I have been working through the problems on Project Euler and doing the implementation in C. I recommend this for anyone trying to learn a new language (eg. if you’re trying to learn Python you can implement the problems in Python) or just generally as a fun coding exercise.
Problem 13 is as follows:
Work out the first ten digits of the sum of the following one-hundred 50-digit numbers. 37107287533902102798797998220837590246510135740250 46376937677490009712648124896970078050417018260538 74324986199524741059474233309513058123726617309629 91942213363574161572522430563301811072406154908250 23067588207539346171171980310421047513778063246676 89261670696623633820136378418383684178734361726757 ... 100 lines of this ...
So I’m sure some languages would allow you to easily add large numbers like these, but the challenge is to implement this in C. I felt that thinking of the numbers as a list of digits is probably the way to go, since then you’re really just dealing with arrays of integers.
static const int DIGITS[100][50] = { { 3, 7, 1, 0, 7, ... lots more of this ..., 2, 5, 0 },
{ 4, 6, 3, 7, 6, ... lots more of this ..., 5, 3, 8 },
{ 7, 4, 3, 2, 4, ... lots more of this ..., 6, 2, 9 },
... lots more of this ...
{ 9, 1, 9, 4, 2, ... lots more of this ..., 2, 5, 0 },
{ 2, 3, 0, 6, 7, ... lots more of this ..., 6, 7, 6 },
{ 8, 9, 2, 6, 1, ... lots more of this ..., 7, 5, 7 },
{ 2, 8, 1, 1, 2, ... lots more of this ..., 7, 3, 8 },
};Now I basically did the addition as you were taught in 1st or 2nd grade - run down the column and then carry over any digit greater than 9. So first, initialize an array to hold the sum. I made an educated guess that the result wouldn’t be more than 100 digits.
int* initializeBuffer(int bufferSize) {
int* ptr = (int*)malloc(bufferSize * sizeof(int));
for (int i = 0; i < bufferSize; i++) {
ptr[i] = 0;
}
return ptr;
}
int main(void) {
int resultBufferSize = 100;
int* resultBufferPtr = (int*)malloc(resultBufferSize * sizeof(int));
}Then run down every single column and sum the values.
for (int column = 49; column >= 0; column--) {
long columnSum = 0;
for (int row = 0; row < 100; row++) {
columnSum += DIGITS[row][column];
}
resultBufferPtr[49-column] = columnSum;
}The aim is to have resultBuffer contain the digits of the complete sum, but basically in reverse - I found it easier to think through in that way. So the ‘ones’, would be at resultBufferPtr[0], the ‘tens’ at resultBufferPtr[1], the ‘hundreds’ at resultBufferPtr[2], etc. Right now I’ve just summed the columns though, so the resultBuffer contains values greater than 9 in pretty much every position (I verified this by printing out the whole buffer). So sticking with the idea of addition in 1st grade, we just need to carry over any value greater than 9.
int indexResultBuffer = 0;
while (1) {
if (resultBufferPtr[indexResultBuffer] > 9) {
resultBufferPtr[indexResultBuffer+1] += resultBufferPtr[indexResultBuffer] / 10;
resultBufferPtr[indexResultBuffer] %= 10;
}
bool foundNonZero = false;
for (int i = indexResultBuffer; i < resultBufferSize && !foundNonZero; i++) {
foundNonZero = resultBufferPtr[i] > 0;
}
if (foundNonZero) {
indexResultBuffer++;
} else {
break;
}
}The foundNonZero bit at the end is basically saying we don’t know how many digits the sum will have at the end, so we only know we’re done when the rest of the array contains only zeros. There are definitely easier ways to do that, but we end up with an array containing the digits of the sum (in reverse) with indexResultBuffer - 1 being the number of digits.
printf("The entire sum is ");
for (int i = indexResultBuffer - 1; i >= 0; i--) {
printf("%d", resultBufferPtr[i]);
}
printf("\n");
printf("The first 10 digits is ");
for (int i = indexResultBuffer - 1; i >= indexResultBuffer - 10; i--) {
printf("%d", resultBufferPtr[i]);
}
printf("\n");That allows us to sum to a 52-digit number, neat. Let’s not forget to free the memory we’ve allocated!
free(resultBufferPtr);You can find the code for this problem (and other fun challenges on Project Euler) on Github.