分治法与大数乘法

发表于 2023-03-21 更新于 2023-04-01 分类于算法 Waline：本文字数： 5.6k 阅读时长 ≈ 5 分钟

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

问题分析

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

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

	十万	万	千	百	十	个
				9	9	9
				9	9	9
9*9					8	1
90*9				8	1	0
900*9			8	1	0	0
9*90				8	1	0
90*90			8	1	0	0
900*90		8	1	0	0	0
9*900			8	1	0	0
90*900		8	1	0	0	0
900*900	8	1	0	0	0	0
	9	9	8	0	0	1

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

方法引入

分治法

思想

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

适用情况

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

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

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

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

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

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

使用步骤

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

方法实现

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

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

则

\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}

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

方法函数设计

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

string cal(string, string);

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

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

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

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

// 长度对半分
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的乘法分解为 $a_1*b_1$ 、 $a_1*b_0$ 、 $a_0*b_1$ 、 $a_0*b_0$ 四个乘法，这里也设计四个递归表达式对应四个乘法。

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');

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

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

return res;

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

具体流程

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

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

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

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

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函数就能实现任意大数的乘法运算，解题的关键在于考虑将两个大数的乘法分解为多个小数的乘法。

源代码

完整源代码参考如下

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

参考资料

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

分治算法详解