题目

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

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

或者

求 1234567891011121314151617181920 * 2019181716151413121110987654321 的乘积结果

分析

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

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

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

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

Karatsuba于1960年发明在 O(nlog23)

步骤的猜想。

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

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

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

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

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

进一步计算，

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

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

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

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

最终结果就是：

以上就是使用分治的方式计算乘法的原理。上面这个算法，由 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]

1、大数相加

int或者long类型的数据往往满足不了数据容量的要求，这时需要用到数组或者字符串进行操作。考虑到数据的位数并不是一个确定的值，运用string来处理可以简化思维。在进行运算之前，需要明确下面几点要求：

1.将两组数据中位数大的放在前面，方便后面处理；

2.字符转数字，减去‘0’；数字转字符加上‘0’；

3.进位考虑

4.最高位时进位判断

string BigPlus(string num1,string num2){
    //默认使得num1位数大于num2，方便后续运算。
    if(num1.size()<num2.size()){
        string temp=num2;
        num2=num1;
        num1=temp;
    }
    int lenth1=num1.size(),lenth2=num2.size(),flag=0,a,b,sum;//初始化位数、进位标志、定义转换数字a、b和sum
    while(lenth1>0){//lenth1总是大于等于lenth2
        a=num1[lenth1-1]-'0';//转换为数字
        if(lenth2>0){
            b=num2[lenth2-1]-'0';//转换为数字
        }
        else{
            b=0;//num2位数加完了
        }
        sum=a+b+flag;//当前位加进位
        if(sum>=10){//进位判断
            flag=1;//进位标记
            num1[lenth1-1]='0'+sum%10;//取个位
        }
        else{
            flag=0;//进位标记清除
            num1[lenth1-1]='0'+sum;
        }
        //每次向前进位
        lenth1--;
        lenth2--;
    }
    if(flag){
        num1="1"+num1;//当最高位进位，在前面加1
    }
    return num1;//返回得到的和
}

2、大数相乘

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

示例 1: 输入: num1 = “2”, num2 = “3”. 输出: “6”

class Solution {
public:
	string multiply(string num1, string num2) {
		if (num1 == "0" || num2 == "0") return "0";
		int n1 = num1.length() - 1;
		int n2 = num2.length() - 1;
		vector<int> mul(n1 + n2 + 2);
//编译器默认初始化为0  n位数和m位数相乘最多为m+n位数。
//乘数 num1 位数为 MM，被乘数 num2 位数为 NN， num1 x num2 结果 res 最大总位数为 M+N
//num1[i] x num2[j] 的结果为 tmp(位数为两位，"0x","xy"的形式)，其第一位位于 res[i+j]，第二位位于 res[i+j+1]。
//11*12 =132  1和2相乘的结果为2的下标加1的下标，假设1的下标代表2乘了几个10（0下标开始的话）
		for (int i = n1; i >= 0; i--)
			for (int j = n2; j >= 0; j--) { //11 12
				int bitmul = (num1[i] - '0')*(num2[j] - '0');//两个位上的数的乘积
				bitmul += mul[i + j + 1];//先加低位，判断是否有新的进位

				mul[i + j] += bitmul / 10;//高位
				mul[i + j + 1] = bitmul % 10;//低位
			}

		//去掉前导0
		int i = 0;
		while (i < n1 + n2 + 1 && mul[i] == 0)
			i++;
		int index = i;
		string multi=string(n1+n2+2-i,'0');
		for (; i < n1 + n2 + 2; i++)
			multi[i-index]=(mul[i]+'0');//string类型的append函数
		return multi;
	}
};

1.1实验内容

实现两个十进制大整数的相乘（100位以上），输出乘法运算的结果。

1.2实验环境

Microsoft Visual Studio 2017+masm 32

1.3实验思路

1.3.1数据读入

大数相乘由于输入的数字过大而不能用一个dword来存储，所以需要使用数组来存取每一位，每一位大小范围在0-9中，按位读取输入，所以首先需要按照字符读取输入，将读入的两个数存储为两个字符数组中。

   ;键盘分别输入A和B，并存储为byte数组
    invoke printf, offset inputMsg
    invoke scanf,addr input,addr numCharA
    invoke printf,offset inputMsg
    invoke scanf,addr input,addr numCharB

1.3.2 将字符转为数字并反转存储

由于读入数据的是字符，所以需要先将字符转为数字，才能进行乘法，其次在大数相乘中，我们模拟手算乘法的过程，即乘数之间从低位向高位相乘并按位存储，再进行进位处理。所以，在转换为数字的过程中，我们通过将字符处理为数字后压栈，再依次退栈存储到数字数组中，实现将数字反转，这样再模拟乘法过程中可以从数组开始循环至数组结束。

 invoke strlen,numChar
        mov len,eax
        mov ecx,len
        L3:
            ;eax=esi[i]
            movzx eax,byte ptr[esi]
            ;减去'0',得到数字0-9
            sub eax,30H
            ;压栈
            push eax
            ;esi=numChar[i+1]
            inc esi
            loop L3
        mov ecx,len
        mov esi,numInt
        L4:
            ;从栈中弹出数据，依次存储到numInt中，达到反序的目的
            pop eax
            mov dword ptr[esi],eax
            ;esi+4，因为numInt为dword数组，4个偏移量为一个数据
            add esi,4
            loop L4
        ;再次调用strlen，使eax=len，返回时从eax即可读出len的值
        invoke strlen,numChar

1.3.3 模拟乘法

模拟乘法的过程为模拟手算乘法的过程，即x的第i位与y的第j位相乘时，结果存储到结果的第i+j位。

  mov ebx, -1
OuterLoop: 
    inc ebx
    cmp ebx, lengthA
    jnb endLoop1 ;如果ebx >= lengthA,结束循环
    xor ecx, ecx
InnerLoop:
    xor edx, edx
    mov eax, dword ptr numIntA[4 * ebx]
    mul numIntB[4 * ecx] ;numIntA[4 * ebx] * numIntB[4 * ecx]结果放在EDX:EAX中,最大9*9 = 81也不会超过8个字节，所以结果只在EAX中
    mov esi, ecx
    add esi, ebx ;esi = ecx + ebx，即两个下标之和
    add result[4 * esi], eax ;把两个位相乘的结果加到result的相应位上
    inc ecx
    cmp ecx, lengthB 
    jnb OuterLoop ;无符号数ecx>=lengthB时，下标超过lengthB - 1时跳出内层循环重新进行外层循环
    jmp InnerLoop   ;不超过则继续进行内层循环
endLoop1:
    mov ecx, lengthA
    add ecx, lengthB
    inc ecx ;ecx = lengthA + lengthB + 1
    mov esi, offset lengthC
    mov [esi], ecx ;将ecx赋给lengthC

1.3.4 进位

从低位到高位依次将结果的第i+1位加上第i位除10的结果，第i位等于第i位模10的结果。即result[i+1]+=result[i]/10，result[i]+=result[i]%10。

CarryCul:
    cmp ebx, ecx
    jnb endLoop2 ;ebx >= ecx跳到endLoop2,跳出求进位的循环
    mov eax, result[4  * ebx]
    xor edx, edx
    div radix
    add result[4 * ebx + 4], eax ;result[i+1] += result[i]/10
    mov result[4 * ebx], edx ;result[i] = result[i] % 10
    inc ebx
    jmp CarryCul
endLoop2: 
    mov ecx, lengthC ;让MoveZero从最后一位开始检查

1.3.5 清0

当i位数与j位数相乘时，最终结果不一定是i+j位，从最高位依次检测结果数组中的值是否为0，为0则长度减1。

MoveZero:
    cmp dword ptr result[4 * ecx], 0
    jnz endwhile1 ;result的末位不为0
    dec ecx ;每检测到一个0，实际长度减一 
    jmp MoveZero
endwhile1:
    inc ecx ;实际长度为最大下标加一
    mov esi, offset lengthC
    mov [esi], ecx ;将ecx赋给lengthC

1.3.6结果转为字符再输出

由于计算的结果也是反序存储在结果数组中，所以需要将结果数组反转并且转换位字符数组才能输出，所以采用和1.3.2类似的方法，将数字转为字符并压栈，循环结束后将字符依次退栈存储到结果中，最后输出字符串即可。

int2str_reverse proc far C uses eax esi ecx 
    mov ecx, lengthC ;结果的长度为循环的次数
    mov esi, 0 
L1:
    mov eax, dword ptr result[4 * esi] 
    add eax, 30H ;数字0~9 + '0'得到字符'0'~'9'
    push eax
    inc esi
    loop L1 ;把dword数组numInt全部入栈，最高位先入栈，最低位最后入栈

    mov ecx, lengthC
    mov esi, 0
L2:
    pop eax
    mov byte ptr resultChar[esi], al ;依次出栈，把低八位存在resultChar的对应位置中，最低位先出栈，存在resultChar的最低位中
    inc esi
    loop L2
    ret
int2str_reverse endp

1.3.6 对负数进行处理

由于读入数据是一个一个字符的读入，所以如果读入的数字第一位为“-”，维护一个negativeFlag初始为0。若读入一个符号，则将其异或，则0变1，再有一个负号则1变0，当negativeFlag为1时，输出时则在结果之间输出负号。

;esi=numChar首地址
    mov esi,numChar
    ;eax=esi[0]
    movzx eax,byte ptr[esi]
    ;Symbol=eax，判断numChar第一个字符是否为负号
    mov Symbol,eax
    .if Symbol==2DH
        ;为负数，negativeFlag异或1
        xor negativeFlag,1
        ;调用strlen得到numChar的长度
        invoke strlen,numChar
        ;减去负号
        sub eax,1
        mov len,eax
        mov ecx,len
        ;esi=numChar[1]
        inc esi

1.4实验结果

1.5完整代码

Chris_William/BIT-X86-Experiment (gitee.com)https://gitee.com/chris-william/bit-x86-experiment