Calculating a very large integer

Question

How do I add two big integers, I have tried using arrays and it still has some bugs. Ex: A 23 digit + 25 digit positive integer (2345235... + 34634235....)

I've tried using arrays to separate the digits and eventually add them up, but there is still some bugs, like when 999 + 999, it will output 998, or when it is 24 digits + 25 digits, the code becomes complicated. Is there any easy way of doing it?

#include <stdio.h>

int main(void)
{
    int length_A, length_B, times;
    long long int A[101] = {0};
    long long int B[101] = {0};
    long long int total[101] = {0};

    scanf("%d", &length_A);
    for (int i = 0; i < length_A; i++)
    {
        scanf("%1lld", &A[i]);
    }
    scanf("%d", &length_B);
    for (int j = 0; j < length_B; j++)
    {
        scanf("%1lld", &B[j]);
    }

    if (length_A > length_B)
    {
        times = length_A - length_B;
        for (int l = 0; l < times; l++)
        {
            total[l] = A[l];
        }
        for (int k = 0; k < length_B; k++)
        {
            total[k+times] = A[k+times] + B[k];
            if(total[k+times] > 9)
            {
                if (total[k+times-1] == 9)
                {
                    total[k+times-2]++;
                    total[k+times-1] = 0;
                    total[k+times] -= 10;
                }
                else if (total[k+times-1] < 9)
                {
                    total[k+times-1]++;
                    total[k] -= 10;
                }
            }
        }
        for (int z = 0; z < length_B; z++)
        {
            printf("%lld", total[z]);
        }
    }
    else if (length_B > length_A)
    {
        times = length_B - length_A;
        for (int k = 0; k < length_B; k++)
        {
            for (int l = 0; l < times; l++)
            {
                total[l] = B[l];
            }
            total[k+times] = A[k] + B[k+times];
            if(total[k] > 9)
            {
                if (total[k-times] == 9)
                {
                    total[k-times-1]++;
                    total[k-times] = 0;
                    total[k] -= 10;
                }
                else
                {
                    total[k-1]++;
                    total[k] -= 10;
                }
            }
        }
        for (int z = 0; z < length_B; z++)
        {
            printf("%lld", total[z]);
        }
    }
    else
    {
        for (int k = 0; k < length_B; k++)
        {
            total[k] = A[k] + B[k];
            if(total[k] > 9)
            {
                if (total[k-1] == 9)
                {
                    total[k-2]++;
                    total[k-1] = 0;
                    total[k] -= 10;
                }
                else
                {
                    total[k-1]++;
                    total[k] -= 10;
                }
            }
        }
        for (int z = 0; z < length_B; z++)
        {
            printf("%lld", total[z]);
        }
    }
}

Answer 1

• OP's code adds from most significant to least. It is easier and more common to add from least significant (highest index) to most significant, keeping track of the carry.

 // General algorithm.  Needs more work to handle if the lengths of a, b differ.
 carry = 0;
 for (index = least; index >= most; index--) {
   sum = a[index] + b[index] + carry;
   total[index] = sum %10;
   carry = sum / 10;
 }

• OP's code does not handle if the sum to the 2 numbers forms a carry out of the most significant digit. In fact it attempts to set total[-1] = ....

// After the above loop
if (carry) {
  // Shift sum digits "right"
  // Then set the new most significant digit.
}

• The total array should be 1 longer than A, B to handle the potential last "carry".

• long long int A[101] = {0}; is excessive. signed char A[101] = {0}; is sufficient to save all 1 and 2 decimal digit values.

---

Is there any easy way of doing it?

Maybe, easy for some, a challenge for learners.
A key strategy is divide and conquer.
Consider separating input from addition and output.
Form 3 functions.

// Return length
int big_number_read(int max_length, signed char *destination);

// Return length
int big_number_add(int max_sum_length, signed char *sum, 
    int a_length, signed char *a, 
    int b_length, signed char *b);

void big_number_print(int a_length, signed char *a);

Then form main()

#define BIGINT_LEN_MAX 100
int main() {
  signed char a[BIGINT_LEN_MAX];
  signed char b[BIGINT_LEN_MAX];
  signed char sum[BIGINT_LEN_MAX + 1];
  int length_a = big_number_read(BIGINT_LEN_MAX, a);
  int length_b = big_number_read(BIGINT_LEN_MAX, b);
  int length_sum = big_number_add(BIGINT_LEN_MAX + 1, sum,
      length_a, a, length_b, b);
  big_number_print(length_sum, sum);
}

Answer 2

Your approach to computing a large addition has problems:

• you should compute the digits from the least significant one to the most significant one, propagating a carry as you would using high school arithmetics.
• you should make room for an extra digit should the sum produce a number larger than both A and B.
• you should use a smaller type to hold the digits: long long int is overkill for values in the range 0 to 9. You could even use the character representation of the digits directly.

Here is a modified version of your code:

#include <stdio.h>

int main(void) {
    int length_A, length_B, length_total, i, j, k, carry;
    int A[101], B[101], total[101];

    if (scanf("%d", &length_A) != 1 || length_A <= 0 || length_A > 100)
        return 1;
    for (i = 0; i < length_A; i++) {
        if (scanf("%1d", &A[i]) != 1)
            return 1;
    }
    if (scanf("%d", &length_B) != 1 || length_B <= 0 || length_B > 100)
        return 1;
    for (i = 0; i < length_B; i++) {
        if (scanf("%1d", &B[i]) != 1)
            return 1;
    }

    length_total = (length_A > length_B) ? length_A + 1 : length_B + 1;
    carry = 0;
    i = length_A;
    j = length_B;
    k = length_total;
    while (i > 0 && j > 0) {
        int digit = A[--i] + B[--j] + carry;
        carry = (digit > 9);
        digit -= carry * 10;
        total[--k] = digit;
    }
    while (i > 0) {
        int digit = A[--i] + carry;
        carry = (digit > 9);
        digit -= carry * 10;
        total[--k] = digit;
    }
    while (j > 0) {
        int digit = B[--j] + carry;
        carry = (digit > 9);
        digit -= carry * 10;
        total[--k] = digit;
    }
    if (carry) {
        total[--k] = carry;
    }
    while (k < length_total) {
        printf("%d", total[k++]);
    }
    printf("\n");
    return 0;
}

Here is an alternative that reads the numbers as strings without a length prefix and uses the strings directly:

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

int main(void) {
    char A[101], B[101], total[102];

    if (scanf(" %100[0-9] %100[0-9]", A, B) != 2)
        return 1;

    int length_A = strlen(A);
    int length_B = strlen(B);
    int length_total = (length_A > length_B) ? length_A + 1 : length_B + 1;
    int i = length_A;
    int j = length_B;
    int k = length_total;
    int carry = 0;
    total[k] = '\0';
    while (i > 0 && j > 0) {
        int digit = A[--i] + B[--j] + carry - '0';
        carry = (digit > '9');
        digit -= carry * 10;
        total[--k] = (char)digit;
    }
    while (i > 0) {
        int digit = A[--i] + carry;
        carry = (digit > '9');
        digit -= carry * 10;
        total[--k] = (char)digit;
    }
    while (j > 0) {
        int digit = B[--j] + carry;
        carry = (digit > '9');
        digit -= carry * 10;
        total[--k] = (char)digit;
    }
    if (carry) {
        total[--k] = (char)(carry + '0');
    }
    printf("%s\n", total + k);
    return 0;
}