How to implement a Integer Array Adder for big integers?

Question

Since C doesn't support Big Integers as JAVA, I am trying to implement a integer adder function which takes two integer arrays as parameter and returns a pointer to their sum which is again an array. Here is my code.

#include<stdio.h>
#include<stdlib.h>
int max(int a,int b) {
    return a < b ? b : a;
}

int* decimalAdder (int* p, int* q) {
    int size1, size2, i;
    size1 = sizeof(p) / sizeof(int);
    size2 = sizeof(q) / sizeof(int);
    int m = max(size1, size2) + 1;
    int* c = (int*)malloc(m * sizeof(int));
    int carry = 0;
    for(i=0 ; i<m ; i++) {
        c[i] = 0;
        if(i < size1 && i < size2) {
            c[i] += p[i] + q[i] + carry;
            if(c[i] >= 10) {
                c[i] = c[i] % 10;
                carry = 1;
            }
            else
                carry = 0;
        }
        else if(i < size1) {
            c[i] += p[i] + carry;
            if(c[i] >= 10) {
                c[i] = c[i] % 10;
                carry = 1;
            }
            else
                carry = 0;
        }
        else if(i < size2) {
            c[i] += q[i] + carry;
            if(c[i] >= 10) {
                c[i] = c[i] % 10;
                carry = 1;
            }
            else
                carry = 0;
        }
        else
            c[i] += carry;
    }
    return c;
}

//Test program
int main() {
    int a[] = {7, 5, 3, 6};
    int b[] = {3, 5, 3};
    int* sum;
    int i;
    sum = decimalAdder(a, b);
    int size = sizeof(sum) / sizeof(int);
    for(i = size ; i >= 0 ; i--)
        printf("%d", sum[i]);
    free(sum);
    sum=NULL;
    return 0;
}

It Outputs 10 Where I'm going wrong? What am I missing?

Answer 1

As noted in the comments, sizeof(p) and sizeof(q) are the same as sizeof(int *). You need to pass the true array sizes as arguments to decimalAdder().

So first, change decimalAdder() to receive the sizes:

int *decimalAdder (int *p, size_t size1, int *q, size_t size2) {
    int i;
    int m = max(size1, size2) + 1;
    int *c = malloc(m * sizeof(int));
    /* ... */
}

You ask how to determine the size of the arrays to pass it to decimalAdder(). Well, if you dynamically allocated the arrays, then you probably know the size (it's the same you passed to malloc(3) before).

If the arrays are stack allocated (which is the case here), you can use the sizeof() method that you use in main(), but only inside the function that declares the arrays (because as soon as you pass a local array to another function, it decays into a pointer to the first element and you can no longer determine its size).

So in this case you could change main() to:

int main(void) {
    int a[] = {7, 5, 3, 6};
    int b[] = {3, 5, 3};
    size_t size1 = sizeof(a)/sizeof(a[0]);
    size_t size2 = sizeof(b)/sizeof(b[0]);
    int* sum;
    int i;
    sum = decimalAdder(a, size1, b, size2);    
    int size = max(size1, size2);

    for(i = size ; i >= 0 ; i--)
        printf("%d", sum[i]);

    free(sum);
    sum=NULL;

    return 0;
}

Note that int size = sizeof(sum) / sizeof(int); won't work the way you expect: sum is not a true array, it's a pointer to int, so sizeof(sum) is the same as sizeof(int *), not the size of the array you allocated. C doesn't keep track of that, you have to do it yourself (as opposed to Java).

Answer 2

But how to determine the true sizes of p and q if it is unknown?

Like this:

#include<stdio.h>

void returnLen(int length){
    printf("The length of Array is:\t%d\n",length);
}

int main(void){
    int array[] = {7, 5, 3, 6, 1, 9, 3, 6, 2, 10, 55};
    int length = sizeof array / sizeof array[0];

    returnLen(length);
    return 0;
}

Output:

The length of Array is: 11

Answer 3

Because an integer array in C is a simple type, it doesn't carry along with it information about its size in the general case. There are any number of ways to address the problem. Michi's answer is correct for statically allocated arrays and perhaps that will be sufficient for your needs if you always know how many array elements with which you will be working. But, if that's the case then this whole exercise is moot since you could just use macro-ized constants and achieve the same result.

Ultimately what you will end up doing is creating a data structure that can be used to carry along the number of digits (or multi-digit elements). Depending on how this code will be used, something like this might work :

struct myArray{
    int length;
    int *digits;
};

That means you'll have to manage the memory (allocate, free, resize, etc.) for the structure. In addition, you might consider using #include and int64_t or uint64_t as your array elements since you'll be able to use fewer cells to represent a given big int.

The data structure (above) is by no means the only solution. You could use a linked list as well (although that's fairly heavy-weight if all you are going to do is simple arithmetic on the nodes).