CST PA1

1-1 A+B Problem

算法构思

一开始考虑使用普通的高精度乘法处理本题:

使用 $\text{string}$ 存储读入的长正整数 $a = \overline{a_{n - 1}a_{n - 2}\cdots a_1a_0}$, $b = \overline{b_{m - 1}b_{m - 2}\cdots b_1b_0}$, 并逐位计算乘积 $c = \overline{c_{l - 1}c_{l - 2}\cdots c_1c_0}$, 满足 $c_k = (\Sigma a_ib_{k - i} + d_k) / 10$, 其中 $d_k$ 为计算 $c_{k - 1}$ 过程产生的进位溢出, 满足 $d_k = (\Sigma a_ib_{k - 1 - i} + d_{k - 1}) \% 10$.

美中不足的是, 这种处理方法计算次数过多, 消耗时间过长, 因此考虑采用压位高精度乘法, 即在上述算法中乘数的每位数字均存入一个 $8$ 位整数, 而非一个简单的十进制整数. 这样扩大了参与单次计算的数据位数, 进而减少了计算次数, 降低了算法耗时.

由于 $\text{int}$ 的范围为 $[- 2^{31}, 2^{31} - 1]$, 其中 $2^{31} - 1 < 10^8 * 10^8$, 在进行 $8$ 位数运算时可能会产生溢出, 因此不可选用 $\text{int}$ 存储乘数;

注意到 $\text{long long}$ 的范围为 $[- 2^{63}, 2^{63} - 1]$, 其中 $2^{63} - 1 > 10^8 * 10^8$, 因此这里选用 $\text{long long}$ 数组来存储乘数. 本题也就相当于模拟 $100,000,000$ 进制的乘法. 本题算法思路如下:

使用 $\text{long long}$ 数组存储读入的长正整数 $a = \overline{a_{n’ - 1}a_{n’ - 2}\cdots a_1a_0}$, $b = \overline{b_{m’ - 1}b_{m’ - 2}\cdots b_1b_0}$, 其中 $a_i, b_j (1\le i\le n’, 1\le j\le m’)$ 均为 $8$ 位整数. 剩下的仿照上文所述的乘法计算及进位过程即可.

代码中的 mul1、 mul2 数组相当于此处的 $a, b$, 而 answer 数组记录了相应 $c$ 的取值.

参考资料

使用了一个快速将 $\text{string}$ 按每八位读入数组的 $trick$, 主要参考了此文章, 调用了 <stdio.h> 中的 sscanf() 函数.

复杂度估计

算法时间复杂度主要来自乘法运算与进位过程:

... 
// Line 48 
for (int i = 0; i <= LEN; i++) {
    int start = max(0, i + 1 - real_len2);
    int finish = min(i, real_len1 - 1);
    for (int j = start; j <= finish; j++)
        answer[i] += mul1[j] * mul2[i - j]; 
    if (answer[i] >= MAX) {                 
        answer[i + 1] += answer[i] / MAX;
        answer[i] %= MAX;
    }
}
...

对于一组长整数输入$m$、$n$, 算法的时间复杂度为 $O(logm\cdot logn)$;

也即若一组长整数输入的十进制位数分别为$m$、$n$, 那么算法的时间复杂度为 $O(mn)$.

算法空间复杂度主要来自读取并存储运算数的过程:

...
// Line 22
char* num1 = (char*)a.c_str();
char* num2 = (char*)b.c_str();
...
// Line 27
long long mul1[real_len1] = {0};
long long mul2[real_len2] = {0};
long long answer[MAXLEN] = {0};
...