分治法与大数乘法

Entropy Tree Lv4
  2023-03-21 19:55:10 2023-03-21 19:55:10 创建   2023-04-01 08:43:21 2023-04-01 08:43:21 更新    2.2k 字  10 分钟  

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

问题分析

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

首先观察一下，乘法最基础的计算方法——列竖式。以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=a1∗10n/2+a0b=b1∗10m/2+b0a=a_1*10^{n/2}+a_0\\ b=b_1*10^{m/2}+b_0

则

a∗b=(a1∗10n/2+a0)∗(b1∗10m/2+b0)=a1∗b1∗10n/2+m/2+a1∗b0∗10n/2+a0∗b1∗10m/2+a0∗b0\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}

可以发现大数乘法分解成了四个小数乘法，即a1∗b1a_1*b_1、a1∗b0a_1*b_0、a0∗b1a_0*b_1、a0∗b0a_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的乘法分解为a1∗b1a_1*b_1、a1∗b0a_1*b_0、a0∗b1a_0*b_1、a0∗b0a_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 Tree
  • 创建于 : 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 进行许可。
推荐阅读
Go语言基础 Go语言基础 后缀表达式 后缀表达式 Go 工程进阶 Go 工程进阶
推荐阅读
Go语言基础 Go语言基础 后缀表达式 后缀表达式
评论
目录
分治法与大数乘法
  1. 问题分析
  2. 方法引入
    1. 分治法
  3. 方法实现
    1. 方法函数设计
  4. 源代码
  5. 参考资料