Adding Large Numbers in C
As an interesting coding exercise, I have been working through the problems on Project Euler and implementing the solutions in C. I recommend this for anyone trying to learn a new language (e.g., 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
… (total of 100 lines) …
Some languages might 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, ... , 2, 5, 0 },
{ 4, 6, 3, 7, 6, ... , 5, 3, 8 },
{ 7, 4, 3, 2, 4, ... , 6, 2, 9 },
...
{ 9, 1, 9, 4, 2, ... , 2, 5, 0 },
{ 2, 3, 0, 6, 7, ... , 6, 7, 6 },
{ 8, 9, 2, 6, 1, ... , 7, 5, 7 },
{ 2, 8, 1, 1, 2, ... , 7, 3, 8 },
};I performed the addition as taught in early schooling—running down each column and carrying over any digit greater than 9. 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 = initializeBuffer(resultBufferSize);
}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 in reverse—it’s easier to process that way. So the ones place would be at resultBufferPtr[0], the tens at resultBufferPtr[1], the hundreds at resultBufferPtr[2], etc. Right now, I’ve just summed the columns, so resultBuffer contains values greater than 9 in pretty much every position. I verified this by printing out the whole buffer. Sticking with the idea of addition from early schooling, we 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 check ensures we continue processing until 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 most significant digit.