data structure for adding very large numbers?

how will you add numbers like 1234567890123456789012345678901234567890, which can't be specified using开发者_C百科 primitive data types? what kind of data structure will you use?

You will need a C library that implements arbitrary-precision arithmetic. There are many to choose from. One popular choice is GNU Multi-Precision Library.

Apart from using libraries like MAPM and MPIR you can try holding them in a double (if precision is not needed), or rollup your own implementation based on arrays.

Google up on C bignum for alternatives.

This is probably a nice place to start.

I've recently been using MPFR - the GNU Multiple Precision Floating-point computations with correct Rounding library. The API is similar in structure to MAPM, which is quite straight forward to use in my experience.

However, if you are only using integers you will probably get better performance from a multiple precision library that has separate integer types (ie MAPM), as MPFR is dedicated to floating point.

If you only want to add integers, which your question suggests might be the case, then you could simply use strings and implement single-digit addition with a 2D lookup table. If your requirements are more complex, then as others have suggested, you need some sort of library for handling big numbers. Whether you use one of the existing libraries or roll your own is up to you.

I will use STACKS. Numbers can be stored in the stack by putting digit with highest place value first so that digit at ones place should be on the top of stack. Pop the two stacks and add the digits from stacks with the carry which is initially zero. Push the result in the third stack digit by digit. Repeat till both stacks are empty.

For a poor man's bignum addition, you can use C strings:

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

char *bigadd(const char *a, const char *b) {
    size_t alen = strlen(a);
    size_t blen = strlen(b);
    size_t clen = (alen > blen) ? alen : blen;
    char *c = malloc(clen + 2);
    if (c != NULL) {
        size_t i = clen;
        int carry = 0;
        c[i] = '\0';
        while (i > 0) {
            char digit = (alen ? a[--alen] - '0' : 0) +
                (blen ? b[--blen] - '0' : 0) + carry;
            c[--i] = digit - 10 * (carry = digit > '9');
        }
        if (carry) {
            memmove(c + 1, c, clen + 1);
            c[0] = '1';
        }
    }
    return c;
}

int main(int argc, char *argv[]) {
    const char *a = argc > 1 ? argv[1] : "123456890123456890123456890";
    const char *b = argc > 2 ? argv[2] : "2035864230956204598237409822324";
    char *c = bigadd(a, b);
    printf("%s + %s = %s\n", a, b, c);
    free(c);
    return 0;
}