大整数运算

大整数加法

如果有两个很大的整数，如何求出它们的和？

这还不简单？直接用long类型存储，在程序里相加不就行了？

在常见的32位int实现中，C/C++中的int类型能表示的范围是 $-2^{31} \sim 2^{31} - 1$ ，unsigned int类型能表示的范围是 $0 \sim 2^{32} - 1$ ，所以int和unsigned int类型变量都不能保存超过10位的整数。

有时需要参与运算的数可能会远远不止10位，例如计算 $100!$ 的精确值。即便使用能表示很大数值范围的double变量，但是由于double变量只有64位，精度也不足以表示一个超过100位的整数。我们称这种基本数据类型无法表示的整数为大整数。

在小学的时候，老师教我们用列竖式的方式计算两个整数的和。

426709752318

+ 95481253129

= 522191005447

PRO EXCLUSIVE探索不止于此

解锁完整互动实验、进阶解析与精选参考答案。

尊享 Pro 权益

题目

某一位的两个数字为7和8，输入进位为1，本位结果和输出进位分别是什么？

不仅仅是人脑，对于计算机来说同样如此。对于大整数，我们无法一步到位直接算出结果，所以不得不把计算拆解成一个一个子步骤。

可是，既然大整数已经超出了long类型的范围，我们如何来存储这样的整数呢？

存放大整数最简单的方法就是使用数组，可以用数组的每一个元素存储整数的每一个数位。如果给定大整数的最长位数是n，那么按位计算的时间复杂度是 $O(n)$ 。

大整数加法

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

按位运算的次数为 $O(n)$ 。这里提供的C++、Java和Python示例在字符串头部添加字符，会反复复制已有内容，因此这些实现的总时间为 $O(n^2)$ ；C示例使用预分配数组。

这种思路其实还存在一个可优化的地方。我们之前是把大整数按照每一个十进制数位来拆分，比如较大整数的长度有50位，那么需要创建一个51位的数组，数组的每个元素存储其中一位。

真的有必要把原整数拆分得那么细吗？显然不需要，只需要拆分到可以被直接计算的程度就够了。int类型的取值范围是 $-2147483648 \sim 2147483647$ ，最多有10位整数。为了防止溢出，可以把大整数的每9位作为数组的一个元素，进行加法运算。如此一来，占用空间和运算次数，都被压缩了约9倍。

大整数加法优化

在Java中，工具类BigInteger和BigDecimal的底层实现也是把大整数拆分成数组进行运算，与此处的思路大体类似。

题目

两个9位块相加，输入进位至多为1，最大中间和是多少？

大整数乘法

起初对于大整数乘法，认为只要按照大整数相加的思路稍微做一下变形，就可以轻松实现。但是随着深入的学习，才发现事情并没有那么简单。如果沿用大整数加法的思路，通过列竖式求解……

93281

× 2034

373124

279843

000000

186562

189733554

乘法竖式的计算过程可以大体分为两步：

整数B的每一个数位和整数A所有数位依次相乘，得到中间结果。
所有中间结果相加，得到最终结果。

这样的做法确实可以实现大整数乘法，由于两个大整数的所有数位都需要一一彼此相乘。如果整数A的长度为m，整数B的长度为n，那么时间复杂度就是 $O(m * n)$ 。如果两个大整数的长度接近，那么时间复杂度也可以写为 $O(n^2)$ 。

那么有没有优化方法，可以让时间复杂度低于 $O(n^2)$ 呢？

利用分治法可以简化问题的规模，可以把大整数按照数位拆分成两部分。

\begin{aligned} \text{整数1} & = \underbrace{81325}_{A}\underbrace{79076}_{B} \\ \text{整数2} & = \underbrace{9213}_{C}\underbrace{52184}_{D} \end{aligned}

即：

\begin{aligned} \text{整数1} & = A \times 10^5 + B \\ \text{整数2} & = C \times 10^5 + D \end{aligned}

如果把两个大整数的长度抽象为m和n，令 $k = \lfloor m/2 \rfloor$ 、 $l = \lfloor n/2 \rfloor$ ，那么：

\begin{aligned} \text{整数1} & = A \times 10^k + B \\ \text{整数2} & = C \times 10^l + D \end{aligned}

因此：

\begin{aligned} & \text{整数1} \times \text{整数2} \\ & = (A \times 10^k + B) \times (C \times 10^l + D) \\ & = AC \times 10^{k+l} + AD \times 10^k + BC \times 10^l + BD \end{aligned}

为分析复杂度，可以在较短整数前补零，并把共同长度n补为偶数，再按相同位数对半拆分。如此一来，原本长度为n的大整数的1次乘积，被转化成了长度为 $n / 2$ 的大整数的4次乘积。

通过递归把大整数不断地对半拆分，一直拆分到可以直接计算为止。

大整数拆分

但是先别高兴地太早，这个方法真的提高了效率吗？

\begin{aligned} T(n) = \begin{cases} O(1) & n = 1 \\ 4T(n/2) + O(n) & n > 1 \end{cases} \end{aligned}

求解得到：

T(n) = O(n^2)

闹了半天，时间复杂度还是 $O(n^2)$ 啊，白高兴一场。但是努力的方向并没有白费，这里还是有优化的方法的。

在大整数乘法运算中，如果只简单地利用分治法将大整数的位数减半，并不能降低时间复杂度的阶。分治法把两个大整数相乘的问题转化为四个较小整数相乘，性能的瓶颈仍旧在乘法上。

分治算法的时间复杂度方程为 $W(n) = aW(n/b) + f(n)$ ，其中 $a$ 为子问题数， $n / b$ 为子问题规模， $f(n)$ 为划分与合并工作量。当 $a \ge 1$ 、 $b > 1$ ，且存在 $\varepsilon > 0$ 使 $f(n) = O(n^{\log_b a - \varepsilon})$ 时， $W(n) = \Theta(n^{log_ba})$ 。减少 $a$ 是降低 $W(n)$ 的阶的一种途径。利用子问题的依赖问题，可以使某些子问题的解通过组合其它子问题的解而得到。

题目

递推式T(n)=4T(n/2)+O(n)的复杂度是多少？

那么，怎样才能减少乘法运算的次数呢？哪怕由四次乘法变成三次乘法也好呀。通过对之前的乘法等式做一些调整，可以减少乘法的次数。

\begin{aligned} & \text{整数1} \times \text{整数2} \\ & = (A \times 10^{n/2} + B) \times (C \times 10^{n/2} + D) \\ & = AC \times 10^n + AD \times 10^{n/2} + BC \times 10^{n/2} + BD \\ & = AC \times 10^n + (AD + BC) \times 10^{n/2} + BD \\ & = AC \times 10^n + (AD - AC - BD + BC + AC + BD) \times 10^{n/2} + BD \\ & = AC \times 10^n + ((A - B)(D - C) + AC + BD) \times 10^{n/2} + BD \end{aligned}

这样一来，原本的4次乘法和3次加法，转变成了3次乘法和6次加法。

骗人！最后式子里明明包含五次乘法啊！

AC出现了两次，BD也出现了两次，这两个乘积分别只需计算一次就行了，所以总共只需要三次乘法。

\begin{aligned} T(n) = \begin{cases} O(1) & n = 1 \\ 3T(n/2) + O(n) & n > 1 \end{cases} \end{aligned}

求解得到：

T(n) = O(n^{log_2{3}}) \approx O(n^{1.59})

题目

改写后的乘法式中AC和BD各出现两次，为什么仍只需要3次乘法？

计算1234 × 5678，把每个整数拆成高两位和低两位：A=12，B=34，C=56，D=78，基数为100。只计算AC、BD、(A−B)(D−C)三个乘积。

写出三个乘积以及AD+BC如何由它们得到。
按位权合并结果，说明AC和BD为什么不用重复计算。

大整数运算

大整数加法

如果有两个很大的整数，如何求出它们的和？

这还不简单？直接用long类型存储，在程序里相加不就行了？

在小学的时候，老师教我们用列竖式的方式计算两个整数的和。

426709752318

+ 95481253129

= 522191005447

PRO EXCLUSIVE探索不止于此

解锁完整互动实验、进阶解析与精选参考答案。

尊享 Pro 权益

题目

某一位的两个数字为7和8，输入进位为1，本位结果和输出进位分别是什么？

不仅仅是人脑，对于计算机来说同样如此。对于大整数，我们无法一步到位直接算出结果，所以不得不把计算拆解成一个一个子步骤。

可是，既然大整数已经超出了long类型的范围，我们如何来存储这样的整数呢？

大整数加法

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

按位运算的次数为 $O(n)$ 。这里提供的C++、Java和Python示例在字符串头部添加字符，会反复复制已有内容，因此这些实现的总时间为 $O(n^2)$ ；C示例使用预分配数组。

大整数加法优化

在Java中，工具类BigInteger和BigDecimal的底层实现也是把大整数拆分成数组进行运算，与此处的思路大体类似。

题目

两个9位块相加，输入进位至多为1，最大中间和是多少？

大整数乘法

93281

× 2034

373124

279843

000000

186562

189733554

乘法竖式的计算过程可以大体分为两步：

整数B的每一个数位和整数A所有数位依次相乘，得到中间结果。
所有中间结果相加，得到最终结果。

那么有没有优化方法，可以让时间复杂度低于 $O(n^2)$ 呢？

利用分治法可以简化问题的规模，可以把大整数按照数位拆分成两部分。

\begin{aligned} \text{整数1} & = \underbrace{81325}_{A}\underbrace{79076}_{B} \\ \text{整数2} & = \underbrace{9213}_{C}\underbrace{52184}_{D} \end{aligned}

即：

\begin{aligned} \text{整数1} & = A \times 10^5 + B \\ \text{整数2} & = C \times 10^5 + D \end{aligned}

如果把两个大整数的长度抽象为m和n，令 $k = \lfloor m/2 \rfloor$ 、 $l = \lfloor n/2 \rfloor$ ，那么：

\begin{aligned} \text{整数1} & = A \times 10^k + B \\ \text{整数2} & = C \times 10^l + D \end{aligned}

因此：

\begin{aligned} & \text{整数1} \times \text{整数2} \\ & = (A \times 10^k + B) \times (C \times 10^l + D) \\ & = AC \times 10^{k+l} + AD \times 10^k + BC \times 10^l + BD \end{aligned}

通过递归把大整数不断地对半拆分，一直拆分到可以直接计算为止。

大整数拆分

但是先别高兴地太早，这个方法真的提高了效率吗？

\begin{aligned} T(n) = \begin{cases} O(1) & n = 1 \\ 4T(n/2) + O(n) & n > 1 \end{cases} \end{aligned}

求解得到：

T(n) = O(n^2)

闹了半天，时间复杂度还是 $O(n^2)$ 啊，白高兴一场。但是努力的方向并没有白费，这里还是有优化的方法的。

题目

递推式T(n)=4T(n/2)+O(n)的复杂度是多少？

那么，怎样才能减少乘法运算的次数呢？哪怕由四次乘法变成三次乘法也好呀。通过对之前的乘法等式做一些调整，可以减少乘法的次数。

\begin{aligned} & \text{整数1} \times \text{整数2} \\ & = (A \times 10^{n/2} + B) \times (C \times 10^{n/2} + D) \\ & = AC \times 10^n + AD \times 10^{n/2} + BC \times 10^{n/2} + BD \\ & = AC \times 10^n + (AD + BC) \times 10^{n/2} + BD \\ & = AC \times 10^n + (AD - AC - BD + BC + AC + BD) \times 10^{n/2} + BD \\ & = AC \times 10^n + ((A - B)(D - C) + AC + BD) \times 10^{n/2} + BD \end{aligned}

这样一来，原本的4次乘法和3次加法，转变成了3次乘法和6次加法。

骗人！最后式子里明明包含五次乘法啊！

AC出现了两次，BD也出现了两次，这两个乘积分别只需计算一次就行了，所以总共只需要三次乘法。

\begin{aligned} T(n) = \begin{cases} O(1) & n = 1 \\ 3T(n/2) + O(n) & n > 1 \end{cases} \end{aligned}

求解得到：

T(n) = O(n^{log_2{3}}) \approx O(n^{1.59})

题目

改写后的乘法式中AC和BD各出现两次，为什么仍只需要3次乘法？

计算1234 × 5678，把每个整数拆成高两位和低两位：A=12，B=34，C=56，D=78，基数为100。只计算AC、BD、(A−B)(D−C)三个乘积。

写出三个乘积以及AD+BC如何由它们得到。
按位权合并结果，说明AC和BD为什么不用重复计算。

大整数运算

大整数运算

大整数加法

大整数加法：从个位传递进位

知识测验

知识测验

大整数乘法

知识测验

知识测验

用三个乘积算出结果

大整数运算

大整数运算

大整数加法

大整数加法：从个位传递进位

知识测验

知识测验

大整数乘法

知识测验

知识测验

用三个乘积算出结果