# Reducing steps for long addition program

This is a program that I wrote to add two numbers together that are too large for the C language to store. It stores the numbers as strings instead and processes one digit at a time. But I suspect that the program could be done in fewer steps. In what ways can I reduce the size of my program? Where am I taking more steps than necessary?

#include <stdio.h>
#include <string.h>

int main()
{
char *a = "1490438498359508";
char *b = "1575390843059845";
char *sum = "";
char str[15] = "";
char src[512];
int carry = 0;
int alength = strlen(a);
int blength = strlen(b);
int n;
int i;
int c, d;

for (n=1; n<blength+1; n++) {
int c=0, d=0;
i = 0;
c = a[alength-n]-48;
d = b[blength-n]-48;
i = c+d;
if (carry == 1) {
i=i+1;
}
if (i > 9) {
i = i-10;
carry=1;
} else {
carry=0;
}
int aInt = i;
char str[15] = "";
sprintf(str, "%d", aInt);
strcat(src, str);

}
int nlength = strlen(src);
int x;
for (x=0; x<nlength+1; x++) {
printf("%c", src[nlength-x]);
}
printf("\n");
return 0;
}


### Big Picture

• Function: This code ought to be packaged into a function, not just in main(). I propose char *add(const char *a, const char *b).
• Bug: You assume that a and b are the same length. If that turns out not to be the case, then you'll either ignore the most significant digits of a (wrong answer) or access the bytes preceding the beginning of a (garbage answer or crash).
• Carrying: You ignore the carry bit at the end of the loop.
• Buffers: You allocated 15-byte and 512-byte buffers. Why those lengths? You should assume that an attacker will try to overflow your buffers with ridiculously long input, regardless of how large you make your fixed-size buffers.

### Variables

• Unused and redeclared variables: Compiling with warnings turned on (I used clang -Wall -o add add.c

add.c:8:11: warning: unused variable 'sum' [-Wunused-variable]
char *sum = "";
^
add.c:9:10: warning: unused variable 'str' [-Wunused-variable]
char str[15] = "";
^
add.c:16:9: warning: unused variable 'c' [-Wunused-variable]
int c, d;
^
add.c:16:12: warning: unused variable 'd' [-Wunused-variable]
int c, d;
^
4 warnings generated.


Redeclaring str, c, and d is pretty sloppy. Fortunately it didn't cause a bug. You want to avoid a giant block of declarations, and declare the variables as close as possible to the point of use.

### Mechanics

• Magic numbers: What's 48? For clarity, write '0' instead.
• int → char: Calling sprintf() seems like overkill — why not use the inverse technique and add '0'? If you wanted to use sprintf(), though, you could do without aInt (just use i) and str and strcat() (just sprintf() to the end of src).
• Initialization: In the loop, there's no need to set c, d, and i to 0, when you're going to assign the useful values right away anyway. (The harm is just to the verbosity of your code. The compiler can optimize these assignments away for you.)
• Avoid conditionals: In the loop, if if-else are unnecessary.

Cleaning up the loop using the remarks above…

char *srcEnd = src;
for (int n = 1; n <= blength; n++) {
int c = a[alength - n] - '0',
d = b[blength - n] - '0';
int i = c + d + carry;
carry = i / 10;
i = i % 10;

*srcEnd++ = (char)(i + '0');
}
if (carry) {
*srcEnd++ = (char)(carry + '0');
}
*srcEnd = '\0';


There's more work necessary to fix the same-length assumption, but I'll leave that as an exercise.

1) It seems that you assumed length of a and b are the same. But if a has a bigger length than b you don't process all digits! Your loop should go over maximum of lengths of a and b and whenever one operand has no digit any more, use 0.

2) You can write these lines

i = c+d;
if (carry == 1) {
i=i+1;
}


like this:

i = c + d + carry


use arithmetic operations when branches are not necessary.

3) The result of addition has always at most one digit more than the bigger operand. So you can allocate a string once and avoid concatenation in each iteration (just put the result digit in its right place).

4) You can reduce number of iterations by using the fact that you can add in higher bases! This way instead of a string, use an integer array and treat the operands, say in base 10000. Now each digit in this base is a 4 digit number in base 10. Everything will be the same, except for setting the value of carry. With base 10^4, you reduced number of iteration to one-forth. You can go further till where integer range supports safely (10^8).