四川省建设质量工程协会网站,logo设计在线生成免费商标,深圳推广公司是什么,wordpress建立个人博客戳蓝字“CSDN云计算”关注我们哦#xff01;如何用程序实现大整数相乘呢#xff1f;在上一篇文章 漫画#xff1a;如何实现大整数相乘#xff1f;#xff08;上#xff09; 当中#xff0c;我们介绍了两种思路#xff1a;1.像列竖式一样#xff0c;把两整数按位依次相… 戳蓝字“CSDN云计算”关注我们哦如何用程序实现大整数相乘呢在上一篇文章 漫画如何实现大整数相乘上 当中我们介绍了两种思路1.像列竖式一样把两整数按位依次相乘这个思路的时间复杂度是On^2。2.利用分治法把每个大整数分成高位和低位两部分转化成四个较小的乘积。这个思路的时间复杂度同样是On^2。那么有什么样的优化方案可以使时间复杂度优于On^2呢我们今天一起来研究下。如何做调整呢其实很简单连小学生都会这样一来原本的4次乘法和3次加法转变成了3次乘法和6次加法。这样一来时间复杂度是多少呢假设两个长度为n的大整数相乘整体运算规模是T(n) 。刚才我们说过两个大整数相乘可以被拆分成三个较小的乘积所以在第一次分治时T(n)和T(n/2)有如下关系T(n) 3T(n/2) f(n)其中f(n)是6次加法的运算规模f(n)的渐进时间复杂度很明显是O(n)。此时让我们回顾一下master定理设常数a 1b 1如果一个算法的整体计算规模 T(n) a T(n / b) f(n)那么则有如下规律对于T(n) 3T(n/2) f(n)这个关系式来说 a3 b2。把a和b的值以及f(n)的时间复杂度带入到master定理的第一个规律也就是下面的规律发现正好符合条件。怎么符合条件呢推导过程如下所以我们的平均时间复杂度是2 和 1.59 之间的差距看似不大但是当整数长度非常大的时候两种方法的性能将是天壤之别。下面展示一下实现代码。我们的代码非常复杂在这里只作为参考最重要的还是解决问题的思路/** * 大整数乘法 * param bigNumberA 大整数A * param bigNumberB 大整数B */public static String bigNumberMultiply(String bigNumberA, String bigNumberB) { boolean isNegative false; if ((bigNumberA.startsWith(-) bigNumberB.startsWith(-)) || (!bigNumberA.startsWith(-) !bigNumberB.startsWith(-))) { // 两数同符号的情况 bigNumberA bigNumberA.replaceAll(-, ); bigNumberB bigNumberB.replaceAll(-, ); } else if ((bigNumberA.startsWith(-) !bigNumberB.startsWith(-)) || (!bigNumberA.startsWith(-) bigNumberB.startsWith(-))) { // 两数不同符号的情况 bigNumberA bigNumberA.replace(-, ); bigNumberB bigNumberB.replace(-, ); isNegative true; } // 如果两数长度之和小于10直接相乘返回 if (bigNumberA.length() bigNumberB.length() 10) { // 计算乘积 int tmp (Integer.parseInt(bigNumberA) * Integer.parseInt(bigNumberB)); if (tmp 0) { return 0; } String value String.valueOf(tmp); if(isNegative){ value - value; } return value; } // 公式 AC * 10^n((A-B)(D-C)ACBD) * 10^(n/2)BD当中的a,b,c,d String a, b, c, d; if (bigNumberA.length() 1) { a 0; b bigNumberA; } else { if (bigNumberA.length() % 2 ! 0) { bigNumberA 0 bigNumberA; } a bigNumberA.substring(0, bigNumberA.length() / 2); b bigNumberA.substring(bigNumberA.length() / 2); } if (bigNumberB.length() 1) { c 0; d bigNumberB; } else { if (bigNumberB.length() % 2 ! 0) { bigNumberB 0 bigNumberB; } c bigNumberB.substring(0, bigNumberB.length() / 2); d bigNumberB.substring(bigNumberB.length() / 2); } // 按最大位数取值以确定补零数目 int n bigNumberA.length() bigNumberB.length() ? bigNumberA.length() : bigNumberB.length(); //t1,t2为中间运算结果t3为乘法运算完毕的结果 String t1, t2, t3; String ac bigNumberMultiply(a, c); String bd bigNumberMultiply(b, d); //t1(A-B)(D-C) t1 bigNumberMultiply(bigNumberSubtract(a, b), bigNumberSubtract(d, c)); //t2(A-B)(D-C)ACBD t2 bigNumberSum(bigNumberSum(t1, ac), bd); //t3 AC * 10^n((A-B)(D-C)ACBD) * 10^(n/2)BD t3 bigNumberSum(bigNumberSum(Power10(ac, n), Power10(t2, n/2)), bd).replaceAll(^0, ); if (t3 ) return 0; if(isNegative){ return - t3; } return t3;}/** * 大整数加法 * param bigNumberA 大整数A * param bigNumberB 大整数B */public static String bigNumberSum(String bigNumberA, String bigNumberB) { if (bigNumberA.startsWith(-) !bigNumberB.startsWith(-)) { return bigNumberSubtract(bigNumberB, bigNumberA.replaceAll(^-, )); } else if (!bigNumberA.startsWith(-) bigNumberB.startsWith(-)) { return bigNumberSubtract(bigNumberA, bigNumberB.replaceAll(^-, )); } else if (bigNumberA.startsWith(-) bigNumberB.startsWith(-)) { return - bigNumberSum(bigNumberA.replaceAll(^-, ), bigNumberB.replaceAll(^-, )); } //1.把两个大整数用数组逆序存储数组长度等于较大整数位数1 int maxLength bigNumberA.length() bigNumberB.length() ? bigNumberA.length() : bigNumberB.length(); int[] arrayA new int[maxLength1]; for(int i0; i bigNumberA.length(); i){ arrayA[i] bigNumberA.charAt(bigNumberA.length()-1-i) - 0; } int[] arrayB new int[maxLength1]; for(int i0; i bigNumberB.length(); i){ arrayB[i] bigNumberB.charAt(bigNumberB.length()-1-i) - 0; } //2.构建result数组数组长度等于较大整数位数1 int[] result new int[maxLength1]; //3.遍历数组按位相加 for(int i0; iresult.length; i){ int temp result[i]; temp arrayA[i]; temp arrayB[i]; //判断是否进位 if(temp 10){ temp - 10; result[i1] 1; } result[i] temp; } //4.把result数组再次逆序并转成String StringBuilder sb new StringBuilder(); //是否找到大整数的最高有效位 boolean findFirst false; for (int i result.length - 1; i 0; i--) { if(!findFirst){ if(result[i] 0){ continue; } findFirst true; } sb.append(result[i]); } return sb.toString();}/** * 大整数减法 * param bigNumberA 大整数A * param bigNumberB 大整数B */public static String bigNumberSubtract(String bigNumberA, String bigNumberB) { int compareResult compare(bigNumberA, bigNumberB); if (compareResult 0) { return 0; } boolean isNegative false; if (compareResult -1) { String tmp bigNumberB; bigNumberB bigNumberA; bigNumberA tmp; isNegative true; } //1.把两个大整数用数组逆序存储数组长度等于较大整数位数1 int maxLength bigNumberA.length() bigNumberB.length() ? bigNumberA.length() : bigNumberB.length(); int[] arrayA new int[maxLength1]; for(int i0; i bigNumberA.length(); i){ arrayA[i] bigNumberA.charAt(bigNumberA.length()-1-i) - 0; } int[] arrayB new int[maxLength1]; for(int i0; i bigNumberB.length(); i){ arrayB[i] bigNumberB.charAt(bigNumberB.length()-1-i) - 0; } //2.构建result数组数组长度等于较大整数位数1 int[] result new int[maxLength1]; //3.遍历数组按位相加 for(int i0; iresult.length; i){ int temp result[i]; temp arrayA[i]; temp - arrayB[i]; //判断是否进位 if(temp 0){ temp 10; result[i1] -1; } result[i] temp; } //4.把result数组再次逆序并转成String StringBuilder sb new StringBuilder(); //是否找到大整数的最高有效位 boolean findFirst false; for (int i result.length - 1; i 0; i--) { if(!findFirst){ if(result[i] 0){ continue; } findFirst true; } sb.append(result[i]); } String value sb.toString(); if (isNegative) { value - value; } return value;}// 比较大小private static int compare(String x, String y) { if (x.length() y.length()) { return 1; } else if (x.length() y.length()) { return -1; } else { for (int i 0; i x.length(); i) { if (x.charAt(i) y.charAt(i)) { return 1; } else if (x.charAt(i) y.charAt(i)) { return -1; } } return 0; }}// 扩大10的n次方倍public static String Power10(String num, int n) { for (int i 0; i n; i) { num 0; } return num;}public static void main(String[] args) { String x 1513143; String y 9345963; System.out.println(bigNumberMultiply(x, y));}需要注意的是这段实现代码只适用于两个大整数长度相等的情况。如果想求解长度不等的整数相乘只需要对代码做微小的改动有兴趣的小伙伴没有试一试。文章转自程序员小灰1.微信群添加小编微信color_ld备注“进群姓名公司职位”即可加入【云计算学习交流群】和志同道合的朋友们共同打卡学习2.征稿投稿邮箱liudancsdn.net微信号color_ld。请备注投稿姓名公司职位。推荐阅读下一次 IT 变革边缘计算Edge computing为什么 ofo 彻底凉了| 畅言AI in 美团吃喝玩乐背后的黑科技无业务不技术那些誓用区块链重塑的行业发展怎么样了Windows 成“弃子”Linux 终上位突发12306 脱库 410 万用户数据究竟从何泄漏可替代Android的6大开源移动操作系统程序员求助被领导强行要求写Bug该怎么办网友的回答让我笑翻程序员抢票姿势 ↓交朋友还能抢票为交流学习请备注姓名公司职位学校专业点击“阅读原文”打开 CSDN App 阅读更贴心
