大整数相乘(分治法）

「爱情、让人受尽委屈。」 2022-09-11 14:13 526阅读 0赞

## **分治法的原理** ##

讨论问题时，先来了解一下什么是分治法。

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

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5b-Y6K6w5pe26Ze055qE5bCP55m9_size_16_color_FFFFFF_t_70_g_se_x_16][]

## 通过大整数相乘问题来了解分治法 ##

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

## 算法分析 ##

首先将X和Y分成A，B，C，D  
此时将X和Y的乘积转化为图中的式子，把问题转化为求解式子的值  
看起来好像有点变化，分析一下：对这个式子，我们一共要进行4次 n / 2的乘法（AC2次， AD， BC）和 3次加法，因而该算法的时间复杂度为：

T(n) = 4 \* T(n / 2) + θ(n)  
通过master定理可以求得 T(n) = θ(n ^ 2)，跟小学算法的时间复杂度没有区别。

但是我们再来看看，我们是否可以用加法来换取乘法？因为多一个加法操作，也是常数项，对时间复杂度没有影响，如果减少一个乘法则不同。

XY=AC2^n+\[(A-B)(D-C)+AC+BD\]2^n/2+BD

现在的时间复杂度为：

T(n) = 3 \* T(n / 2) + θ(n)，通过master定理求得，T(n) = O(n^log2(3) ) = O(n^1.59 )。

## Master定理： ##

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5b-Y6K6w5pe26Ze055qE5bCP55m9_size_20_color_FFFFFF_t_70_g_se_x_16][]

## **Master定理实例：** ##

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5b-Y6K6w5pe26Ze055qE5bCP55m9_size_20_color_FFFFFF_t_70_g_se_x_16 1][]

## **时间复杂度O的意义：** ##

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5b-Y6K6w5pe26Ze055qE5bCP55m9_size_20_color_FFFFFF_t_70_g_se_x_16 2][]

实例分析  
对X = 1234 和 Y = 5678来分析：

divideConquer（1234， 5678， 4）  
————————————————————————  
X=1234 | A=12 | B=34 | A-B=-22

Y=5678 | C=56 | D=78 | D-C=22

三次递归：  
AC = divideConquer（12， 56， 2）  
BD = divideConquer（34， 78， 2）  
(A-B)(D-C) = divideConquer（-22， 22， 2）

AC递归  
————————————————————————

X=12 | A1=1 | B1=2 | A1-B1=-1

Y=56 | C1=5 | D1=6 | D1-C1=1

A1\*C1 = divideConquer（1， 5， 1） = 5  
B1\*D1 = divideConquer（2， 6， 1） = 12  
（A1-B1） \* （D1-C1） = divideConquer（-1， 1， 1） = -1；

所以AC递归求得的值为：5 \* 10 ^ 2 + （-1 + 5 + 12）\* 10 + 12 = 672

同理可得 BD = 2652 和 (A-B)(D-C) = -484

最终可得 X \* Y = 7006652

## 代码实现： ##

#include <iostream>
    #include<cmath>
    using namespace std;
    
    #define SIGN(A) ((A > 0) ? 1 : -1) 
    int divideConquer(int X, int Y, int n){
        int sign = SIGN(X) * SIGN(Y);//开始先取出两数乘积的符号 
        long long x = abs(X);
        long long y = abs(Y);
        if(x == 0 || y == 0){
            return 0;
        }else if(n == 1){
            return sign * x * y;
        }else{
            long long A = (int) x / pow(10, (int)(n / 2));//取出数字左半边的部分 
            long long B = x - A * pow(10, n / 2);//取出数字右半边的部分 
            long long C = (int) y / pow(10, (int)(n / 2));
            long long D = y - C * pow(10, n / 2);
            long long AC = divideConquer(A, C, n / 2);//左边数字 
            long long BD = divideConquer(B, D, n / 2);//右边数字 
            long long 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(){
        long long x, y;
    	int n;
    	cout << "请输入两个数字：";
    	cin >> x >> y;
    	cout << endl; 
    	cout << "请输入数字的位数：";
    	cin >> n;
    	cout << endl;
    	cout << "x 和 y的乘积为: " << divideConquer(x, y, n); 
    }

## 结果： ##

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5b-Y6K6w5pe26Ze055qE5bCP55m9_size_16_color_FFFFFF_t_70_g_se_x_16 2][]

## 此算法局限性： ##

最多只能算4位的整数的相乘，要是99999\*99999就会出现溢出的现象。

## 优化算法：（没太看的懂） ##

[【分治算法之大整数乘法】---C++实现\_追光者♂的博客-CSDN博客][---C_-CSDN]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5b-Y6K6w5pe26Ze055qE5bCP55m9_size_16_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/ad326234eb6743f9accce407ed93772c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5b-Y6K6w5pe26Ze055qE5bCP55m9_size_16_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/4583230c557749cc9da27349b92f3ad8.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5b-Y6K6w5pe26Ze055qE5bCP55m9_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/aeb98599e3f14e45a98e53cb65362446.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5b-Y6K6w5pe26Ze055qE5bCP55m9_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/c92313f438b44b17b695cb564573ef1b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5b-Y6K6w5pe26Ze055qE5bCP55m9_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/33fa03641e3c47f9acaa129d7786b80b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5b-Y6K6w5pe26Ze055qE5bCP55m9_size_16_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/e07c21d6733b426faf8abfce2765ddf6.png
[---C_-CSDN]: https://blog.csdn.net/qq_44731019/article/details/109367811