分治法解决大整数相乘问题

1. 题目描述

大数乘法法运算跟一般的减法运算是不同的，在面对基本数据类型容量有限而导致无法存储特大数字的情况下，本文采用分治策略的方法来解决大数减运算问题。

输入：两个代表整数的字符串a和b,规定a>=b,a,b>0。

输出：返回表示结果整数的字符串。

2.解决思路——分治策略

2.1题目情景代入

假如现在要求两个大整数相乘的乘积，如1234 * 1234（这里为了了分析简便，所以不举形如1234567891234567这样的大整数，不必要在此纠结），那么按照我们小学学的乘法，就是用乘数的每一项去和1234相乘，这样很明显，算法的时间复杂度是O(n^2)，效率很低下，那么有没有一种更好的方式？我们可以使用分治法来解决。

2.1.1什么是分治法

分治法的意思就是，分而治之，也就是把一个问题，拆分成几个小问题，最后再汇总解决的方法

2.1.2通过大整数相乘理解分治的策略

我们首先将两个数字A和B各自分成前后两段，当然这种时候可能存在两边数字长度不一样，而且比较长的一边不是偶数导致无法整除的方法，所以我们采用前方填充0的办法把两个数字填充成长度大于最长部分的前方填充0的偶长字符串。

然后，可以把$A$分成$A1,A2$,同时将$B$分成$B1,B2$，然后原本的计算公式就变成了$A1 * B1 * 10^N + (A1 * B2 + A2 * B1) * 10^{N/2} + A2 * B2$,这样一来，递归每一步的时间复杂度就变成了$O(n)$，主要是加法，分治则包括四个子问题，每个子问题的规模是原本的1 / 2 , 也就是$T ( n ) = 4 T ( n / 2 ) + O ( n ) $, 一层层递归就是$n+ 4 ∗ n / 2 + . . . + 4 l o g 2 n ∗ 1$, 然后后面我们用一个换底公式把最后一项改一下，结果就是$n^{log_24}$也就是$n^2 $, 我们这里可以直接用最大项，当然其实就不那么看，我们也可以大致得出，这个复杂度如果算上一些小的项目可能已经比原本的竖式算法还要大了，为此，我们必须要想办法去把复杂度降下来。降低时间复杂度的方法就是改一下我们的公式，$(A1∗B2+A2∗B1)=(A1−A2)∗(B2−B1)+A1∗B1+A2∗B2$,观察这个式子，其中的$A1 * B1$和$A2 * B2$都被复用了，也就是说相较于前面式子这个只需要计算三次了，很明显，时间复杂度降到了$O(n^{{log3.5/2})$,这时候我们就能基本证明复杂度降低了。就算是我们单步骤中增加了减法，我们的系数变大，但在n变得足够大的时候也是会比$O(n}2)$ )小的。

但是从算法中可以看到，计算过程中可能出现负数，在计算的过程中，需要考虑到负数，所以对此做一些分类讨论，首先就是要对同号相乘和异号相乘进行分类，然后在计算减法的时候也要进行分类讨论，比较两者的绝对值，被减数的绝对值比减数大的情况和比减数小的都要进行分类，计算过程中，我们同样都是采取从后往前计算的方式，采用借位的方式。

3.算法实现

3.1如何处理相乘的正负数问题

本文中是使用的宏定义一个SIGN函数，对给出数据的值进行一个判断给出相应的正负标识，真正处理结果的时候，只需要对此拿出来进行正负判定就行了。

3.2怎么按照分治策略的思想来写递归函数呢？

首先，在前面的分析当中，我们只是考虑的当前这个大整数，但是，大多时候真正计算的时候，他经过一次的分治后的数仍然还是大整数，也就是我们从一个大的问题（求最后结果）走到了一个小的问题（大问题衍生出来的分支也是和大问题一个性质的问题），这样会一直迭代下去，直到衍生出的小问题不会出现大问题当中的大整数，此时就会按照着先前走的分支，往回走，这就是递归的实现、

现在我们理清了思路，对于递归函数，我们首先要写出终止递归条件，然后按照分治，使得问题衍生，依次进入到相应下的函数。最后返回正确的答案。

3.3代码实现

#include<cstdio>
#include<cmath>

using namespace std;
typedef long long ll;
#define SIGN(A) ((A > 0) ? 1 : -1) //定义的符号函数

int divideConquer(int X, int Y, int n){
    int sign = SIGN(X) * SIGN(Y);
    //不管三七二十一，先都变成正数，后续再处理正负号
    int x = abs(X);
    int y = abs(Y);
    if(x == 0 || y == 0)//递归结束标志
        return 0;
    else if(n == 1)
        return sign * x * y;//此时一定不再是大整数问题
    else
    {
        //处理大整数分治时的数据，前面的公式推导
        int A = (int) x / pow(10, (int)(n / 2));
        int B = x - A * pow(10, n / 2);
        int C = (int) y / pow(10, (int)(n / 2));
        int D = y - C * pow(10, n / 2);
        int AC = divideConquer(A, C, n / 2);
        int BD = divideConquer(B, D, n / 2);
        int ABDC = divideConquer((A - B), (D - C), n / 2) + AC + BD;
        return sign * (AC * pow(10 , n) + ABDC * pow(10, (int)(n / 2)) + BD); 
    }
}

int main(){
    
    ll x, y, n;//给出的大整数有可能会爆int（就是超出int类型）
    scanf("%d%d%d", &x, &y, &n);
    
    printf("x 和 y的乘积为：%d", divideConquer(x, y, n));
}