题目
编写两个任意位数的大数相乘的程序，给出计算结果。比如：
题目描述： 输出两个不超过100位的大整数的乘积。
输入： 输入两个大整数，如1234567 和 123
输出： 输出乘积，如：151851741
或者
求 1234567891011121314151617181920 * 2019181716151413121110987654321 的乘积结果
分析
所谓大数相乘（Multiplication algorithm），就是指数字比较大，相乘的结果超出了基本类型的表示范围，所以这样的数不能够直接做乘法运算。
参考了很多资料，包括维基百科词条Multiplication algorithm，才知道目前大数乘法算法主要有以下几种思路：
- 模拟小学乘法：最简单的乘法竖式手算的累加型；
- 分治乘法：最简单的是Karatsuba乘法，一般化以后有Toom-Cook乘法；
- 快速傅里叶变换FFT：（为了避免精度问题，可以改用快速数论变换FNTT），时间复杂度O(N lgN lglgN)。具体可参照Schönhage–Strassen algorithm；
- 中国剩余定理：把每个数分解到一些互素的模上，然后每个同余方程对应乘起来就行；
- Furer’s algorithm：在渐进意义上FNTT还快的算法。不过好像不太实用，本文就不作介绍了。大家可以参考维基百科Fürer’s algorithm
解法
我们分别实现一下以上算法，既然不能直接使用乘法做运算，最简单最容易想到的办法就是模拟乘法运算。
1、模拟乘法手算累加
7 8 9 6 5 2 × 3 2 1 1 ----------------- 7 8 9 6 5 2 <---- 第1趟 7 8 9 6 5 2 <---- 第2趟 .......... <---- 第n趟 ----------------- ? ? ? ? ? ? ? ? <---- 最后的值用另一个数组表示
如上所示，乘法运算可以分拆为两步：
- 第一步，是将乘数与被乘数逐位相乘；
- 第二步，将逐位相乘得到的结果，对应相加起来。
这有点类似小学数学中，计算乘法时通常采用的“竖式运算”。用Java简单实现了这个算法，代码如下：
/** * 大数相乘 - 模拟乘法手算累加 */ public static Integer[] bigNumberMultiply(int[] arr1, int[] arr2){ ArrayList<Integer> result = new ArrayList<>(); //中间求和的结果 //arr2 逐位与arr1相乘 for(int i = arr2.length - 1; i >= 0; i--){ int carry = 0; ArrayList<Integer> singleList = new ArrayList<>(); //arr2 逐位单次乘法的结果 for(int j = arr1.length - 1; j >= 0; j--){ int r = arr2[i] * arr1[j] + carry; int digit = r % 10; carry = r / 10; singleList.add(digit); } if(carry != 0){ singleList.add(carry); } int resultCarry = 0, count = 0; int k = 0; int l = 0; int offset = arr2.length - 1 - i; //加法的偏移位 ArrayList<Integer> middleResult = new ArrayList<>(); //arr2每位乘法的结果与上一轮的求和结果相加，从右向左做加法并进位 while (k < singleList.size() || l < result.size()) { int kv = 0, lv = 0; if (k < singleList.size() && count >= offset) { kv = singleList.get(k++); } if (l < result.size()) { lv = result.get(l++); } int sum = resultCarry + kv + lv; middleResult.add(sum % 10); //相加结果从右向左（高位到低位）暂时存储，最后需要逆向输出 resultCarry = sum / 10; count++; } if(resultCarry != 0){ middleResult.add(resultCarry); } result.clear(); result = middleResult; } Collections.reverse(result); //逆向输出结果 return result.toArray(new Integer[result.size()]); }
看了以上的代码，感觉思路虽然很简单，但是实现起来却很麻烦，那么我们有没有别的方法来实现这个程序呢？答案是有的，接下来我来介绍第二种方法。
2、模拟乘法累加 - 改进
简单来说，方法二就是先不算任何的进位，也就是说，将每一位相乘，相加的结果保存到同一个位置，到最后才计算进位。
例如：计算98×21,步骤如下
9 8 × 2 1 ------------- (9)(8) <---- 第1趟: 98×1的每一位结果 (18)(16) <---- 第2趟: 98×2的每一位结果 ------------- (18)(25)(8) <---- 这里就是相对位的和，还没有累加进位
这里唯一要注意的便是进位问题，我们可以先不考虑进位，当所有位对应相加，产生结果之后，再考虑。从右向左依次累加，如果该位的数字大于10，那么我们用取余运算，在该位上只保留取余后的个位数，而将十位数进位（通过模运算得到）累加到高位便可，循环直到累加完毕。
核心代码如下：
/** * 大数相乘方法二 */ 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[]数组的最后一位空置，不可能被占用，我们就响应地把num1的第i位与num2的第j位相乘，结果应该存放在结果的第i+j位上的这个结果往后顺移一位（放到第i+j+1位），最后从右向左累加时就多了一个空间。
3、分治 - Karatsuba算法
Karatsuba于1960年发明将两个n位数相乘的Karatsuba算法。它反证了安德雷·柯尔莫哥洛夫于1956年认为这个乘法需要 $ Omega (n^{2})$ 步骤的猜想。
首先来看看这个算法是怎么进行计算的，见下图：
根据上面的思路，实现的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 就合适了，不用再去弄更复杂的递归乘法。
其中，Java8中的源代码如下：
private static final int MULTIPLY_SQUARE_THRESHOLD = 20; private static final int KARATSUBA_THRESHOLD = 80; private static final int TOOM_COOK_THRESHOLD = 240; public BigInteger multiply(BigInteger val) { if (val.signum == 0 || signum == 0) return ZERO; int xlen = mag.length; if (val == this && xlen > MULTIPLY_SQUARE_THRESHOLD) { return square(); } int ylen = val.mag.length; if ((xlen < KARATSUBA_THRESHOLD) || (ylen < KARATSUBA_THRESHOLD)) { int resultSign = signum == val.signum ? 1 : -1; if (val.mag.length == 1) { return multiplyByInt(mag,val.mag[0], resultSign); } if (mag.length == 1) { return multiplyByInt(val.mag,mag[0], resultSign); } int[] result = multiplyToLen(mag, xlen, val.mag, ylen, null); result = trustedStripLeadingZeroInts(result); return new BigInteger(result, resultSign); } else { if ((xlen < TOOM_COOK_THRESHOLD) && (ylen < TOOM_COOK_THRESHOLD)) { // 采用 Karatsuba algorithm 算法 return multiplyKaratsuba(this, val); } else { // 采用 Toom-Cook multiplication 3路乘法 return multiplyToomCook3(this, val); } } }
我们可以看到，Java8依据两个因数的量级分别使用Karatsuba algorithm 和 Toom-Cook multiplication 算法计算大数乘积。