Addition, but in strings.

[patrink]

This is not a question per se, but instead asking for help to fix a proof-of-concept program.

I wanted to do arithmetic on large numbers, but 32 bits aren't quite big enough, so I created a prototype string addition program that adds up the digits in said strings and returns a final string with the answer. The prototype works (for the most part) but is relatively long for such a short process. It also has a few bugs, and may have more which I missed.

Anyways, I was just wondering what things could be fixed, or what things could I optimize. Any help is appreciated.

[whiteflags]

/*
Large digit addition by Pat.

Preforms addition on 2 strings of digits.
tested on upto 2^10 digits, but capable of 2^31 digits (in theory)
set to 2^20 digits as max, but can be changed

known bugs:
1.) no (real) error checking. I don't know where to begin...
2.) if string[] or n in __add() is defined in __add(), it *may* lead to unexpected results for some reason in MSVC++. Havent tested using GCC.
3.) strcpy() doesn't work. if copied to the strings, it reports an extra '0' at the end of final_string.
    most likely because the for loop in add() is REALLY bad.
4.) when compiling with GCC, it may sometimes return a letter as string[0] if there is no carry. Not exactly sure why. Works fine in MSVC++
    example: (when compiled as "GCC -o add add.c") "3233213123" + 3233213123 = "P6466426246"
	Also happens with single digits ("1" + "1" = "`2")
*/

#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS /* MSVC++ reports a bunch of warnings without this */
#endif

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#ifndef max
#define max(a,b) (((a) > (b)) ? (a) : (b))
#endif
#define strmalloc(x) (char*) malloc(sizeof(char) * x)
#define assert(exp, msg) (!(exp) && printf("Assert: \""#exp"\" triggered a breakpoint in file \"%s\" on line: %d.\n\nError:"#msg"\n\nPress any key to terminate this program.", __FILE__, __LINE__) && getchar() ? exit(1) : (void)0)
#define MAX_NUMBER_OF_DIGITS 1048576

/* __add() is internally by add() to process addition of single digits*/
char __add(char a, char b, char* nextcol, char string[], int n) {
	
	/* convert to int and do calculations here */
	n = atoi(&a) + atoi(&b) + atoi(nextcol);

	/* carry the next number if needed
	NOTE: n is guaranteed to never be over 27 because
	atoi(&num) returns a maximum of 9 for single chars */
	if(n >= 10 && n < 20) { 
		n -= 10; 
		*nextcol = '1';
	}
	else if(n >= 20) { 
		n -= 20;
		*nextcol = '2';
	}
	else 
		*nextcol = '\0';

	/* convert n to char, and return the char */
	sprintf(string, "%d", n);
	return *string;
}

char* add(char *number1, char *number2) {
	/* define lengths, and maxlen so I don't need to call them 6 times per loop */
	size_t len1 = strlen(number1) - 1;
	size_t len2 = strlen(number2) - 1;
	size_t maxlen = max(len1, len2);

	/* define storage string,counter, int & string & nextcol for __add() 
	__add() is used to process each char to make addition possible */

	char *string = strmalloc(maxlen + 2);   /* final string */
	size_t counter = 0;                     
	char *st = strmalloc(2);                /* string to be used in __add(). see Known bugs */
	int n = (int) malloc(sizeof(int));      /* int to be used in __add(). see Known bugs */
	char nextcol = '\0';


	/*loop through both numbers and add them up */
	for(; counter <= maxlen; counter++) {
		/* end-of-string-ptr - counter = add(
											 if(counter > len1) {'\0'} else { end-of-number1-ptr - counter } ,
											 if(counter > len2) {'\0'} else { end-of-number2-ptr - counter } 
											 ) */
		*(string + maxlen - counter+1) = __add(counter > len1 ? '\0' : *(number1 + len1 - counter),  counter > len2 ? '\0' : *(number2 + len2 - counter),   &nextcol, st, n);
		/* FIXME: quite long, and doesn't even work 100% */
	}

	/* last calculation for carry over and make it a NULL terminated string */
	if(nextcol != '\0')
		*string = __add('\0', '\0', &nextcol, st, n);
	*(string + maxlen + 1) = '\0';

	/* return the final string */
	return string;
}

int main() {

	/*allocates 3 strings as number1, 2, and the final string*/
	char *str1 = strmalloc(MAX_NUMBER_OF_DIGITS);
	char *str2 = strmalloc(MAX_NUMBER_OF_DIGITS);
	char *final_string = strmalloc((MAX_NUMBER_OF_DIGITS + 2));

	/* assert if malloc() returned NULL */
	assert(str1 != NULL && str2 != NULL && final_string != NULL, "Not enough memory can be allocated.");

	/* get user input */
	printf("Type in number1: ");
	fgets(str1, MAX_NUMBER_OF_DIGITS, stdin);
	printf("Type in number2: ");
	fgets(str2, MAX_NUMBER_OF_DIGITS, stdin);

	/* call add(), and print answer */
	final_string = add(str1, str2);
	printf("\nFinal calculation = \n%s", final_string);
	
	getchar();
	return 0;
}

Start with all this, I guess? You're doing lots of stupid stuff:
- using the reserved variable name __add

ALL tokens starting with __ or _ and a capital are reserved for use by the implementation of the standard library.

- redefining standard macros like assert()
- using atoi() inappropriately

Taking the address of a character is not enough, atoi() wants a *string*, and you'll get undefined behavior if you don't give it a string. Use the calculation (n - '0') instead.

- converting to a string in __add and then returning a single character.

The calculation (n + '0') is magical as well.

- strmalloc

This macro has no reason for existing. By #include <stdlib.h> you already have a proper declaration for malloc so the return value cast is still unnecessary (like always) and the multiplication with sizeof(char) is nothing important. char is always 1 byte.

Maybe taking a step back and not using esoteric syntax like the ternary operator is a good idea as well. I'm glad you seem to know what it does, but you wrote it in a hurry, didn't you, so it's not like you have a clue what's going on in add().

[anduril462]

You aren't the first person to come across this problem. In fact, there are very few problems that haven't been encountered before. You should always remember that, and then search for existing solutions. Googling something like "big number libraries" or "big number arithmetic" would turn up plenty of feature rich and highly optimized libraries for what you need. But in the interest of your edification:

1. Your strmalloc macro is silly, and involves casting malloc, which is generally frowned upon.
2. Your assert macro should be called something else. assert is part of the standard C library.
3. Don't start identifiers with a _ or a double __. They're reserved for the implementation, and could result in symbol conflicts. Rename __add to something like add_digit.
4. Six calls to malloc, but you never free anything. There should be a corresponding free for every malloc.
5. You are abusing malloc. Only malloc when needed, and assign the result to a pointer. Example of bad code: int n = (int) malloc(sizeof(int));. Just int n; is fine, it reserves space to store an int.
6. If you're going to use a for loop, use the initializer portion as well: for(counter = 0; counter <= maxlen; counter++)
7. You shouldn't pass strings to add_digit, just pass the individual chars. You can treat them like little integers and do regular math that way: digit_sum = (a - '0') + (b - '0');
8. Avoid pointer arithmetic when dealing with arrays (yep, your strmalloc basically gives you an array of chars) unless it's absolutely necessary. *(string + maxlen + 1) = '\0' should be string[maxlen + 1] = '\0'.

That's as far as I wanted to go. You are very thorough, which is good, but your code betrays a serious lack of strings, pointers and memory management, which you really need to resolve. Read our tutorials, and Google for more. Read your textbooks and class notes. Do all the examples until you have it mastered.

I assume you're doing large integer addition only, so for error checking, there's a standard C function called isdigit(). You pass it a character, and it returns true if it's a digit, false otherwise. Make sure you have nothing but digits in the strings entered, and you're fine.

Never worry about optimizing until you know for a fact your code is too slow. That's called pre-optimization, and is a cardinal sin in programming. If your code doesn't work 100%, optimizing it doesn't help, it just produces errors more quickly. Get a fully working algorithm, test it, and only if it's insufferably inefficient should you optimize.

When you have a problem to solve via programming, don't run to the keyboard. Make sure you have a clear understanding of the problem. Come up with a generic solution (algorithm) on paper. Work through your algorithm by hand on some small test cases. Prove it's concept before you code. Then, start writing, in small chunks, testing as you go. That last part is crucial. In your case, the first thing I would have written was add_digit. Then I would have written a main function that ran some basic tests on add_digit and printed out the result and carry for verification. Then I would write my I/O and reverse functions, testing those. Lastly, I would write my core add function.

For your problem, think of how you add by hand. Your pencil and paper method you learned in second grade is a fine way to implement this. I would do the following:

read num1
error check
read num2
error check
reverse num1  // we add from right to left, so this makes our loop handling easier
reverse num2
add num1 and num2
reverse result

[User Name:]

If you can't get GMP installed, iMalc has a good, easy to use, library for this. It's in C++, and based upon C++ features, though. Otherwise, GMP is the way to go.

[patrink]

Thanks for all the input. I realized I'd get criticized for misusing malloc (and not freeing) as much as I did, but in the beginning I needed it. As it stands so far, I can see why "int n = (int) malloc(sizeof(int));" and *almost* all my calls to strmalloc are silly and unnecessary. I'll get working on it.