【算法】大数乘法问题及其高效算法
题目编写两个任意位数的大数相乘的程序,给出计算结果。比如:
或者 求 1234567891011121314151617181920 * 2019181716151413121110987654321 的乘积结果
分析所谓大数相乘(Multiplication algorithm),就是指数字比较大,相乘的结果超出了基本类型的表示范围,所以这样的数不能够直接做乘法运算。 参考了很多资料,包括维基百科词条Multiplication 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;
}
而正好 3、分治 - Karatsuba算法以上两种模拟乘法的手算累加型算法,他们都是模拟普通乘法的计算方式,时间复杂度都是O(n^2),而这个Karatsuba算法,时间复杂度仅有
Karatsuba于1960年发明在
首先来看看这个算法是怎么进行计算的,见下图: 图中显示了计算 接下来,就来证明一下这个算法的正确性。这是一幅来自Karatsuba Multiplication Algorithm – Python Code的图,我们来看看: 我们假设要相乘的两个数是x * y。我们可以把x,y写成:
这里的n是数字的位数。如果是偶数,则a和b都是
进一步计算,
对比之前的计算过程。结果已经呼之欲出了。这里唯一需要注意的两点就是:
我们举例来尝试一下这种算法,比如计算
那么
最终结果就是:
以上就是使用分治的方式计算乘法的原理。上面这个算法,由 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 部分时,可以使用下面的 测试程序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]
参考资料
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |