大数相乘

今天药忘吃喽~ 2022-05-23 11:23 335阅读 0赞

## 题目 ##

编写两个任意位数的大数相乘的程序，给出计算结果。比如：

> 题目描述： 输出两个不超过100位的大整数的乘积。  
> 输入： 输入两个大整数，如1234567 和 123  
> 输出： 输出乘积，如：151851741

或者

求 1234567891011121314151617181920 * 2019181716151413121110987654321 的乘积结果

![70][]

## 分析 ##

所谓大数相乘（Multiplication algorithm），就是指数字比较大，相乘的结果超出了基本类型的表示范围，所以这样的数不能够直接做乘法运算。

参考了很多资料，包括维基百科词条[Multiplication algorithm][]，才知道目前大数乘法算法主要有以下几种思路：

1.  **模拟小学乘法**：最简单的乘法竖式手算的累加型；
2.  **分治乘法**：最简单的是Karatsuba乘法，一般化以后有Toom-Cook乘法；
3.  **快速傅里叶变换FFT**：（为了避免精度问题，可以改用快速数论变换FNTT），时间复杂度O(N lgN lglgN)。具体可参照[Schönhage–Strassen algorithm][Sch_nhage_Strassen algorithm]；
4.  **中国剩余定理**：把每个数分解到一些互素的模上，然后每个同余方程对应乘起来就行；
5.  **Furer’s algorithm**：在渐进意义上FNTT还快的算法。不过好像不太实用，本文就不作介绍了。大家可以参考维基百科[Fürer’s algorithm][F_rer_s algorithm]

## 解法 ##

我们分别实现一下以上算法，既然不能直接使用乘法做运算，最简单最容易想到的办法就是模拟乘法运算。

### 1、模拟乘法累加    ###

简单来说，方法二就是先不算任何的进位，也就是说，**将每一位相乘，相加的结果保存到同一个位置，到最后才计算进位**。

例如：计算98×21,步骤如下

9 8
    × 2 1 -------------
     (9)(8) <---- 第1趟: 98×1的每一位结果 
     (18)(16) <---- 第2趟: 98×2的每一位结果 -------------
     (18)(25)(8) <---- 这里就是相对位的和，还没有累加进位

这里唯一要注意的便是进位问题，我们可以先不考虑进位，当所有位对应相加，产生结果之后，再考虑。从右向左依次累加，如果该位的数字大于10，那么我们用取余运算，在该位上只保留取余后的个位数，而将十位数进位（通过模运算得到）累加到高位便可，循环直到累加完毕。

C++版，完整代码：

#include <iostream>
    #include <vector>
    #include <string>
    using namespace std;
    //大数相乘
    /**
    *num1 乘数1
    *num2 乘数2
    */
    
    void BigMutiple(string num1, string num2){
    
        string res="";
        //两个数的位数
        int m = num1.size(), n = num2.size();
    
        //一个i位数乘以一个j位数，结果至少是i+j-1位数,之多为i+j位
        vector<int> tmp(m + n );
    
        //每一位进行乘法
        for (int i = 0; i < m; i++){
             int a = num1[i] - '0';
            for (int j = 0; j < n; j++){
                int b = num2[j] - '0';
                tmp[i+j+1] += a*b;
            }
        }
    
    	//进行进位处理，注意左侧是大右侧是小
    	for(int k = tmp.size() - 1; k >= 0; k--){
            if(tmp[k] > 10){
                tmp[k - 1] += tmp[k] / 10;
                tmp[k] %= 10;
            }
        }
    
       
    	//如果第0位为0，则最高位没有进位
    	if(tmp[0]==0)
    	{
    		for (int x=1;x<tmp.size();x++){
    			int q=tmp[x];
            
    			printf("%c",(q+'0'));
    		}
    	}
        //如果第0位不为0，则最高位进位
    	else{
    		for (int x=0;x<tmp.size();x++){
    			int q=tmp[x];
    			printf("%c",(q+'0'));
    		}
    	}
    
    }
    
    //测试函数
    int main(){
        string num1, num2;
        while (cin >> num1 >> num2){
    		BigMutiple(num1, num2);
    		printf("\n");
        }
        return 0;
    }

Java版核心代码如下：

/** * 大数相乘方法二 */
    public static int[] bigNumberMultiply2(int[] num1, int[] num2){
        // 分配一个空间，用来存储运算的结果，num1长的数 * num2长的数，结果不会超过num1+num2长
        int[] result = new int[num1.length + num2.length];
    
        // 先不考虑进位问题，根据竖式的乘法运算，num1的第i位与num2的第j位相乘，结果应该存放在结果的第i+j位上
        for (int i = 0; i < num1.length; i++){
            for (int j = 0; j < num2.length; j++){
                result[i + j + 1] += num1[i] * num2[j];  // (因为进位的问题，最终放置到第i+j+1位)
            }
        }
    
        //单独处理进位
        for(int k = result.length-1; k > 0; k--){
            if(result[k] > 10){
                result[k - 1] += result[k] / 10;
                result[k] %= 10;
            }
        }
        return result;
    }

> **！！注意：**这里的进位有个大坑，因为`result[]`数组是从左到右记录相对位的和（还没有进位），而最后的进位是从右向左累加进位，这样的话，如果最高位，也就是最左侧那一位的累加结果需要进位的话，`result[]`数组就没有空间存放了。

而正好`result[]`数组的最后一位空置，不可能被占用，我们就响应地把**num1的第i位与num2的第j位相乘，结果应该存放在结果的第i+j位上**的这个结果往后顺移一位（`放到第i+j+1位`），最后从右向左累加时就多了一个空间。

### 2、分治 - Karatsuba算法 ###

以上两种模拟乘法的手算累加型算法，他们都是模拟普通乘法的计算方式，时间复杂度都是O(n^2)，而这个Karatsuba算法，时间复杂度仅有 *O*(*n*log23)

。下面，我就来介绍一下这个算法。

Karatsuba于1960年发明在 *O*(*n*log23)

步骤内将两个n位数相乘的Karatsuba算法。它反证了安德雷·柯尔莫哥洛夫于1956年认为这个乘法需要 Ω(*n*2)

步骤的猜想。

首先来看看这个算法是怎么进行计算的，见下图：

![Karatsuba Multiplication Algorithm步骤][Karatsuba Multiplication Algorithm]

图中显示了计算`5678 * 1234`的过程，首先是拆分成abcd四个部分，然后分别计算`ac`, `bd`, `(a+b)*(c+d)`，最后再用第三个算式的结果减去前面两个（其实得到的就是`bc+ad`，但是减少了乘法步骤），然后，计算式1后面加4个0，计算式2后面不加，计算式3后面加2个0，再把这三者相加，就是正确结果。

接下来，就来证明一下这个算法的正确性。这是一幅来自[Karatsuba Multiplication Algorithm – Python Code][Karatsuba Multiplication Algorithm _ Python Code]的图，我们来看看：

![Karatsuba算法证明][Karatsuba]

我们假设要相乘的两个数是x \* y。我们可以把x，y写成：

*x*=*a*∗10*n*/2\+*b*

*y*=*c*∗10*n*/2\+*d*

这里的n是数字的位数。如果是偶数，则a和b都是`n/2`位的。如果n是奇数，则你可以让a是`n/2+1`位，b是`n/2`位。（例如a = 12，b = 34；a = 123，b = 45），那么`x*y`就变成了：

*x*∗*y*=(*a*∗10*n*/2\+*b*)∗(*c*∗10*n*/2\+*d*)

进一步计算，

*x*∗*y*=*a*∗*c*∗10*n*\+(*a*∗*d*\+*b*∗*c*)∗10*n*/2\+*b**d*

对比之前的计算过程。结果已经呼之欲出了。这里唯一需要注意的两点就是：

> 1.  `(a * d + b * c)`的计算为了防止两次乘法，应该使用之前的计算
> 2.  这些乘法在算法里应该是递归实现的，数字很大时，先拆分，然后拆分出来的数字还是很大的话，就继续拆分，直到a \* b已经是一个非常简单的小问题为之。这也是分治的思想。

--------------------

我们举例来尝试一下这种算法，比如计算`12345 * 6789`，我们让`a = 12`，`b = 345`。同时`c = 6`，`d = 789`。也就是：

12345=12⋅1000\+3456789=6⋅1000\+789

那么`a*c`，`b*d`的结果如下：

*z*2=*a*∗*c*=12×6=72*z*0=*b*∗*d*=345×789=272205*z*1=(12\+345)×(6\+789)−*z*2−*z*0=283815−72−272205=11538

最终结果就是：

*r**e**s**u**l**t*=*z*2⋅102∗3\+*z*1⋅103\+*z*0*r**e**s**u**l**t*=72⋅106\+11538⋅103\+272205=83810205.

以上就是使用分治的方式计算乘法的原理。上面这个算法，由 Anatolii Alexeevitch Karatsuba 于1960年提出并于1962年发表，所以也被称为 Karatsuba 乘法。

根据上面的思路，实现的Karatsuba乘法代码如下：

/**
     * Karatsuba乘法
     */
    public static long karatsuba(long num1, long num2){
        //递归终止条件
        if(num1 < 10 || num2 < 10) return num1 * num2;
    
        // 计算拆分长度
        int size1 = String.valueOf(num1).length();
        int size2 = String.valueOf(num2).length();
        int halfN = Math.max(size1, size2) / 2;
    
        /* 拆分为a, b, c, d */
        long a = Long.valueOf(String.valueOf(num1).substring(0, size1 - halfN));
        long b = Long.valueOf(String.valueOf(num1).substring(size1 - halfN));
        long c = Long.valueOf(String.valueOf(num2).substring(0, size2 - halfN));
        long d = Long.valueOf(String.valueOf(num2).substring(size2 - halfN));
    
        // 计算z2, z0, z1, 此处的乘法使用递归
        long z2 = karatsuba(a, c);
        long z0 = karatsuba(b, d);
        long z1 = karatsuba((a + b), (c + d)) - z0 - z2;
    
        return (long)(z2 * Math.pow(10, (2*halfN)) + z1 * Math.pow(10, halfN) + z0);
    }

**总结：**

Karatsuba 算法是比较简单的递归乘法，把输入拆分成 2 部分，不过对于更大的数，可以把输入拆分成 3 部分甚至 4 部分。拆分为 3 部分时，可以使用下面的`Toom-Cook 3-way` 乘法，复杂度降低到 O(n^1.465)。拆分为 4 部分时，使用`Toom-Cook 4-way` 乘法，复杂度进一步下降到 O(n^1.404)。对于更大的数字，可以拆成 100 段，使用`快速傅里叶变换FFT`，复杂度接近线性，大约是 O(n^1.149)。可以看出，分割越大，时间复杂度就越低，但是所要计算的中间项以及合并最终结果的过程就会越复杂，开销会增加，因此分割点上升，对于公钥加密，暂时用不到太大的整数，所以使用 Karatsuba 就合适了，不用再去弄更复杂的递归乘法。

## 测试程序 ##

public class LeetcodeTest {
    
        public static void main(String[] args) {
    //        String a = "1234567891011121314151617181920";
    //        String b = "2019181716151413121110987654321";
    
    //        String a = "999999999999";
    //        String b = "999999999999";
    
    //        String a = "24566";
    //        String b = "452053";
    
            String a = "98";
            String b = "21";
    
            char[] charArr1 = a.trim().toCharArray();
            char[] charArr2 = b.trim().toCharArray();
    
            // 字符数组转换为int[]数组
            int[] arr1 = new int[charArr1.length];
            int[] arr2 = new int[charArr2.length];
            for(int i = 0; i < charArr1.length; i++){
                arr1[i] = charArr1[i] - '0';
            }
            for(int i = 0; i < charArr2.length; i++){
                arr2[i] = charArr2[i] - '0';
            }
    
            // 开始计算
            int[] result = LeetcodeTest.bigNumberMultiply2(arr1, arr2);
            System.out.println(a + " * " + b + " = " + Arrays.toString(result).replace(", ", ""));
        }
    }

最后，是测试用例输出结果：

1234567891011121314151617181920 * 2019181716151413121110987654321 = [02492816912877266687794240983772975935013386905490061131076320]
    
    999999999999 * 999999999999 = [999999999998000000000001]
    
    24566 * 452053 = [11105133998]
    
    98 * 21 = [2058]

[70]: /images/20220523/d2c0316b0a6d4de3a8ad14b2896afe10.png
[Multiplication algorithm]: https://en.wikipedia.org/wiki/Multiplication_algorithm
[Sch_nhage_Strassen algorithm]: https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm
[F_rer_s algorithm]: https://en.wikipedia.org/wiki/F%C3%BCrer%27s_algorithm
[Karatsuba Multiplication Algorithm]: /images/20220523/0bfe96ba7f534004866bbf40434df945.png
[Karatsuba Multiplication Algorithm _ Python Code]: https://pythonandr.com/2015/10/13/karatsuba-multiplication-algorithm-python-code/
[Karatsuba]: /images/20220523/a8fb3a88cd954243a06c2e00e924b22e.png