分治法与大数乘法

Entropy Lv4

使用分治法解决大数乘法问题

问题分析

大数乘法问题,由于不限制数据的大小,使用基本数据类型无法直接计算超过其最大表示范围的数据。因此需要考虑对大数进行分解

首先观察一下,乘法最基础的计算方法——列竖式。以999*999为例

十万
999
999
9*981
90*9810
900*98100
9*90810
90*908100
900*9081000
9*9008100
90*90081000
900*900810000
998001

可以看到大数乘法被分解为了多步简单的计算,且每步计算是相互独立的,最后只需要将多步计算的结果累加即可。

方法引入

分治法

思想

将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。

适用情况

分治法能够解决的问题具有以下特征

  1. 该问题的规模缩小到一定的程度就可以很容易地解决。
  2. 问题可以分解为多个规模较小的相同问题,即该问题具有最优子结构
  3. 将该问题所分解出的子问题的解合并就可以得到该问题的解。
  4. 该问题所分解出的各个子问题是相互独立的,即子问题之间不存在公共性的问题。

特征1是大多数问题都能满足的

特征2是使用分治法的前提,也是大部分问题能够满足的

特征3是最关键的,能否在该问题上使用分治法完全取决于特征3

特征4涉及到分治法的效率问题,如果子问题之间不是相互独立的,则分治法需要重复地解决公共的问题,降低效率。针对这个效率问题,就设计出了动态规划法来应对具有重叠子问题的最优子结构问题。

使用步骤

  1. 将原问题分解为多个规模较小、相互独立且和原问题形式相同的子问题。
  2. 若子问题规模足够小则直接解决,否则使用递归进一步分解子问题直到能够解决为止。
  3. 将多个子问题的解返回,通过递归合并为原问题的解。

方法实现

假设有大数a(长度为n)和b(长度为m)。这里使用二分法将大数进行拆分,则大数a、b可拆分为

a=a110n/2+a0b=b110m/2+b0a=a_1*10^{n/2}+a_0\\ b=b_1*10^{m/2}+b_0

ab=(a110n/2+a0)(b110m/2+b0)=a1b110n/2+m/2+a1b010n/2+a0b110m/2+a0b0\begin{aligned} a*b=(a_1*10^{n/2}+a_0)*(b_1*10^{m/2}+b_0)\\ =a_1*b_1*10^{n/2+m/2}+a_1*b_0*10^{n/2}\\+a_0*b_1*10^{m/2}+a_0*b_0 \end{aligned}

可以发现大数乘法分解成了四个小数乘法,即a1b1a_1*b_1a1b0a_1*b_0a0b1a_0*b_1a0b0a_0*b_0。如果分解出来的数字还是过大可以进一步分解。这里考虑将大数a、b分解到只有一位数字的规模进行求解。

方法函数设计

函数原型:以字符串类型传递两个大数

1
string cal(string, string);

先设计对较小规模的方法处理,判断两个字符串长度,将两个字符串转为int进行计算之后再转回字符串返回

1
2
3
4
5
if (a.length() < 2 && b.length() < 2) {
int ai = stoi(a);
int bi = stoi(b);
return to_string(ai * bi);
}

再设计递归表达式,这里使用二分法分解大数。

二分法获取大数的前半部分和后半部分,主要通过substr函数实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 长度对半分
int ahalflen = a.length() / 2;
int bhalflen = b.length() / 2;

// 大整数分成前半部分和后半部分
string ahead = "0";
string atail = "0";

if (a.length() > ahalflen && ahalflen > 0) {
// substr(pos, len) 截取一个字符串从pos位置开始,长度为len的部分
ahead = a.substr(0, ahalflen);
atail = a.substr(ahalflen, a.length() - ahalflen);
} else {
ahead = "0";
atail = a;
}

string bhead = "0";
string btail = "0";
if (b.length() > bhalflen && bhalflen > 0) {
bhead = b.substr(0, bhalflen);
btail = b.substr(bhalflen, b.length() - bhalflen);
} else {
bhead = "0";
btail = b;
}

递归表达式的设计,参考前面将大数a、b的乘法分解为a1b1a_1*b_1a1b0a_1*b_0a0b1a_0*b_1a0b0a_0*b_0四个乘法,这里也设计四个递归表达式对应四个乘法。

1
2
3
4
string ahbh = cal(ahead, bhead);
string atbt = cal(atail, btail);
string ahbt = cal(ahead, btail);
string atbh = cal(atail, bhead);

对乘法的解进行相应的补位。

1
2
3
ahbh.append((a.length() - ahalflen) + (b.length() - bhalflen), '0');
ahbt.append(a.length() - ahalflen, '0');
atbh.append(b.length() - bhalflen, '0');

将四个乘法的解合并并返回,其中add函数是自定义设计的用于大数加法计算的函数

1
2
3
4
5
6
string res = "";
res = add(ahbh, ahbt);
res = add(res, atbh);
res = add(res, atbt);

return res;

关于add函数的设计思路:使用int数组从后往前依次存储大数的每一位数,同时最后的int数组根据实际情况额外存储一位因进位而产生的数字。

具体流程

获取两个大数中最大的长度,反转两个大数字符串从个位数开始计算。

每次计算取出对应位数上的数字转为int进行计算,判断其值是否需要做进位处理。

计算完成后,由于此时字符串是反转的状态,还需要对字符串进行一次反转。

这里的反转的循环从后往前,去除掉高位上不需要的0,同时使用zeroStart来处理需要保留的中间部分的0,将需要保留的数字从后往前拼接起来并返回计算结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
string add(string a, string b) {
int maxlen = max(a.length(), b.length());
int *sum = new int[maxlen]();

reverse(a.begin(), a.end());
reverse(b.begin(), b.end());

for (int i = 0; i < maxlen; i++) {
int a_bit = 0;
int b_bit = 0;
if (i < a.length()) {
// string(num, c) 生成一个字符串,包含num个c字符
a_bit = stoi(string(1, a.at(i)));
}

if (i < b.length()) {
b_bit = stoi(string(1, b.at(i)));
}

sum[i] += (a_bit + b_bit);
if (i < maxlen - 1 && sum[i] > 9) {
sum[i + 1] = sum[i] / 10;
sum[i] %= 10;
}
}

string res = "";
bool zeroStart = true;
for (int i = maxlen - 1; i >= 0; i--) {
if (sum[i] == 0 && zeroStart) {
continue;
}
zeroStart = false;
res.append(to_string(sum[i]));
}
return res;
}

通过add函数和cal函数就能实现任意大数的乘法运算,解题的关键在于考虑将两个大数的乘法分解为多个小数的乘法。

源代码

完整源代码参考如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <algorithm>
#include <iostream>
using namespace std;

string add(string a, string b) {
int maxlen = max(a.length(), b.length());
int *sum = new int[maxlen]();

reverse(a.begin(), a.end());
reverse(b.begin(), b.end());

for (int i = 0; i < maxlen; i++) {
int a_bit = 0;
int b_bit = 0;
if (i < a.length()) {
// string(num, c) 生成一个字符串,包含num个c字符
a_bit = stoi(string(1, a.at(i)));
}

if (i < b.length()) {
b_bit = stoi(string(1, b.at(i)));
}

sum[i] += (a_bit + b_bit);
if (i < maxlen - 1 && sum[i] > 9) {
sum[i + 1] = sum[i] / 10;
sum[i] %= 10;
}
}

string res = "";
bool zeroStart = true;
for (int i = maxlen - 1; i >= 0; i--) {
if (sum[i] == 0 && zeroStart) {
continue;
}
zeroStart = false;
res.append(to_string(sum[i]));
}
return res;
}

string cal(string a, string b) {
// 规模足够小直接返回结果
if (a.length() < 2 && b.length() < 2) {
int ai = stoi(a);
int bi = stoi(b);
return to_string(ai * bi);
}

// 长度对半分
int ahalflen = a.length() / 2;
int bhalflen = b.length() / 2;

// 大整数分成前半部分和后半部分
string ahead = "0";
string atail = "0";

if (a.length() > ahalflen && ahalflen > 0) {
// substr(pos, len) 截取一个字符串从pos位置开始,长度为len的部分
ahead = a.substr(0, ahalflen);
atail = a.substr(ahalflen, a.length() - ahalflen);
} else {
ahead = "0";
atail = a;
}

string bhead = "0";
string btail = "0";
if (b.length() > bhalflen && bhalflen > 0) {
bhead = b.substr(0, bhalflen);
btail = b.substr(bhalflen, b.length() - bhalflen);
} else {
bhead = "0";
btail = b;
}

string ahbh = cal(ahead, bhead);
string atbt = cal(atail, btail);
string ahbt = cal(ahead, btail);
string atbh = cal(atail, bhead);

ahbh.append((a.length() - ahalflen) + (b.length() - bhalflen), '0');
ahbt.append(a.length() - ahalflen, '0');
atbh.append(b.length() - bhalflen, '0');

string res = "";
res = add(ahbh, ahbt);
res = add(res, atbh);
res = add(res, atbt);

return res;
}

int main() {
string a, b;
cin >> a >> b;
cout << cal(a, b);
}

参考资料

看了就会的大整数乘法运算与分治算法

分治算法详解

  • 标题: 分治法与大数乘法
  • 作者: Entropy
  • 创建于 : 2023-03-21 19:55:10
  • 更新于 : 2023-04-01 08:43:21
  • 链接: https://www.entropy-tree.top/2023/03/21/partition-calculate-bigdata/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论