Big Integer Arithmetic

Big-integer addition

How can we add two very large integers?

Isn't that straightforward? Store them as long values and add them in a program.

In common implementations with 32-bit int, C/C++ int ranges from $-2^{31}$ to $2^{31}-1$, and unsigned int from $0$ to $2^{32}-1$. Neither can hold an integer with more than ten decimal digits.

Some calculations require far more than ten digits, such as the exact value of $100!$. A double can represent a large range of magnitudes, but its 64-bit representation lacks the precision for an integer with over 100 digits. Integers beyond the capacity of basic data types are called big integers.

At school, we learn to add integers using a column layout.

Computers face the same issue: the calculation must be broken into smaller steps rather than performed in one operation.

But if the value exceeds the range of long, how can we store it?

The simplest approach uses an array, with one element per digit. If the longer integer has n digits, the digit-by-digit calculation takes $O(n)$ operations.

Big-integer addition

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

char *big_int_add(const char *num1, const char *num2) {
    int num1_len = strlen(num1);
    int num2_len = strlen(num2);
    int len = num1_len > num2_len ? num1_len : num2_len;

    char *number1 = (char *)malloc(sizeof(char) * (len + 1));
    char *number2 = (char *)malloc(sizeof(char) * (len + 1));

    // copy num1 to number1, num2 to number2, and pad the shorter number with leading zeros
    if (num1_len > num2_len) {
        strcpy(number1, num1);
        for (int i = 0; i < num1_len - num2_len; i++) {
            number2[i] = '0';
        }
        strcpy(number2 + num1_len - num2_len, num2);
    } else {
        strcpy(number2, num2);
        for (int i = 0; i < num2_len - num1_len; i++) {
            number1[i] = '0';
        }
        strcpy(number1 + num2_len - num1_len, num1);
    }

    char *result = (char *)calloc(len + 2, sizeof(char));
    int carry = 0;
    for (int i = len - 1; i >= 0; i--) {
        int digit_sum = number1[i] - '0' + number2[i] - '0' + carry;
        carry = digit_sum / 10;
        int digit = digit_sum % 10;
        result[i + 1] = digit + '0';
    }

    if (carry > 0) {
        result[0] = carry + '0';
    } else {
        memmove(result, result + 1, len + 1);
    }

    free(number1);
    free(number2);

    return result;
}

int main() {
    char *result = big_int_add("426709752318", "95481253129");
    printf("%s\n", result);
    free(result);
    return 0;
}

There are $O(n)$ digit operations. The supplied C++, Java, and Python samples prepend characters to strings, repeatedly copying existing content, so these implementations take $O(n^2)$ total time. The C sample uses a preallocated array.

There is still an opportunity to improve this representation. Storing each decimal digit separately means that a 50-digit number needs an array of 51 positions, including room for a possible carry.

Do we really need such small pieces? We only need chunks small enough for direct arithmetic. A signed 32-bit int ranges from $-2147483648$ to $2147483647$, at most ten digits. To avoid overflow during addition, store nine decimal digits per array element. This reduces storage and arithmetic work by roughly a factor of nine.

Java's BigInteger and BigDecimal also use arrays internally, following a broadly similar idea.

Big-integer multiplication

At first, multiplication appears to need only a small adjustment to the addition approach. Further study reveals more complexity. Consider schoolbook long multiplication:

The calculation has two main stages:

1. Multiply every digit of B by all digits of A, obtaining partial results.
2. Add all partial results to obtain the final product.

This works, but every digit of one integer must multiply every digit of the other. For lengths m and n, the time complexity is $O(mn)$, or $O(n^2)$ when their lengths are comparable.

Can we do better than $O(n^2)$?

Divide and conquer can reduce the problem size by splitting each integer into two groups of digits.

That is:

For lengths m and n, let $k=\lfloor m/2\rfloor$ and $l=\lfloor n/2\rfloor$:

Therefore:

For complexity analysis, pad the shorter number with leading zeros and make their common length n even. Split both at the same position. One product of n-digit integers becomes four products of $n/2$-digit integers.

Continue splitting recursively until the pieces can be calculated directly.

But has this actually improved efficiency?

Solving gives:

The complexity is still quadratic! Yet the direction is useful: there is another optimization.

Simply halving the digit count does not lower the complexity order. The original multiplication has become four smaller multiplications, and multiplication remains the bottleneck.

The recurrence is $W(n)=aW(n/b)+f(n)$, where a counts subproblems, $n/b$ is their size, and $f(n)$ measures splitting and combining work. If $a\ge1$, $b>1$, and $f(n)=O(n^{\log_b a-\varepsilon})$ for some $\varepsilon>0$, then $W(n)=\Theta(n^{\log_b a})$. Reducing a is one way to lower the order. Dependencies can allow some subproblem results to be derived from others.

How can we reduce the number of multiplications, even from four to three? Rearrange the product:

Four multiplications and three additions become three multiplications and six additions or subtractions.

Wait—the final expression seems to contain five multiplications!

AC and BD each appear twice, but each product is computed only once and reused. Only three multiplications are needed.

Solving gives: