CODEWITHSUNDEEP
c
user259107
user259107

Reputation: 51

data structure for adding very large numbers?

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

Upvotes: 5

Views: 1779

Answers (6)

chqrlie
chqrlie

Reputation: 144695

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;
}

Upvotes: 1

Sagar Chand
Sagar Chand

Reputation: 260

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.

Upvotes: 0

High Performance Mark
High Performance Mark

Reputation: 78316

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.

Upvotes: 2

James Morris
James Morris

Reputation: 4935

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.

Upvotes: 2

Kornel Kisielewicz
Kornel Kisielewicz

Reputation: 57545

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.

Upvotes: 2

sleske
sleske

Reputation: 83587

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.

Upvotes: 4

Related Questions