漫画：如何实现大整数相乘？（下）

戳蓝字“CSDN云计算”关注我们哦！


如何用程序实现大整数相乘呢？


在上一篇文章  漫画：如何实现大整数相乘？（上） 当中，我们介绍了两种思路：


1.像列竖式一样，把两整数按位依次相乘

640?wx_fmt=png


这个思路的时间复杂度是O（n^2）。



2.利用分治法，把每个大整数分成高位和低位两部分，转化成四个较小的乘积。


640?wx_fmt=png

这个思路的时间复杂度同样是O（n^2）。


那么，有什么样的优化方案，可以使时间复杂度优于O（n^2）呢？我们今天一起来研究下。



640?wx_fmt=jpeg



640?wx_fmt=jpeg


640?wx_fmt=jpeg


640?wx_fmt=jpeg



如何做调整呢？其实很简单，连小学生都会：


640?wx_fmt=png


这样一来，原本的4次乘法和3次加法，转变成了3次乘法和6次加法。


640?wx_fmt=jpeg


640?wx_fmt=jpeg



这样一来，时间复杂度是多少呢？


假设两个长度为n的大整数相乘，整体运算规模是T(n) 。


刚才我们说过，两个大整数相乘可以被拆分成三个较小的乘积，

所以在第一次分治时，T(n)和T(n/2)有如下关系：

T(n) = 3T(n/2) + f(n)

其中f(n)是6次加法的运算规模，f(n)的渐进时间复杂度很明显是O(n)。


此时让我们回顾一下master定理：


设常数a >= 1，b > 1，如果一个算法的整体计算规模 T(n) =  a T(n / b) + f(n)，那么则有如下规律：


640?wx_fmt=png

对于T(n) = 3T(n/2) + f(n)这个关系式来说， a=3， b=2。


把a和b的值，以及f(n)的时间复杂度带入到master定理的第一个规律，也就是下面的规律：


640?wx_fmt=png


发现正好符合条件。


怎么符合条件呢？推导过程如下：


640?wx_fmt=png


所以我们的平均时间复杂度是：

640?wx_fmt=png


2 和 1.59 之间的差距看似不大，但是当整数长度非常大的时候，两种方法的性能将是天壤之别。


640?wx_fmt=jpeg


640?wx_fmt=jpeg


640?wx_fmt=png


下面展示一下实现代码。我们的代码非常复杂，在这里只作为参考，最重要的还是解决问题的思路：


 
 
  1. /**
  2.  * 大整数乘法
  3.  * @param bigNumberA  大整数A
  4.  * @param bigNumberB  大整数B
  5.  */
  6. public static String bigNumberMultiply(String bigNumberA, String bigNumberB) {
  7.     boolean isNegative = false;
  8.     if ((bigNumberA.startsWith("-") && bigNumberB.startsWith("-"))
  9.             || (!bigNumberA.startsWith("-") && !bigNumberB.startsWith("-"))) {
  10.         // 两数同符号的情况
  11.         bigNumberA = bigNumberA.replaceAll("-", "");
  12.         bigNumberB = bigNumberB.replaceAll("-", "");
  13.     } else if ((bigNumberA.startsWith("-") && !bigNumberB.startsWith("-"))
  14.             || (!bigNumberA.startsWith("-") && bigNumberB.startsWith("-"))) {
  15.         // 两数不同符号的情况
  16.         bigNumberA = bigNumberA.replace("-", "");
  17.         bigNumberB = bigNumberB.replace("-", "");
  18.         isNegative = true;
  19.     }
  20.     // 如果两数长度之和小于10，直接相乘返回
  21.     if (bigNumberA.length() + bigNumberB.length() < 10) {
  22.         // 计算乘积
  23.         int tmp = (Integer.parseInt(bigNumberA) * Integer.parseInt(bigNumberB));
  24.         if (tmp == 0) {
  25.             return "0";
  26.         }
  27.         String value = String.valueOf(tmp);
  28.         if(isNegative){
  29.             value = "-" + value;
  30.         }
  31.         return value;
  32.     }
  33.     // 公式 AC * 10^n+((A-B)(D-C)+AC+BD) * 10^(n/2)+BD当中的a,b,c,d
  34.     String a, b, c, d;
  35.     if (bigNumberA.length() == 1) {
  36.         a = "0";
  37.         b = bigNumberA;
  38.     } else {
  39.         if (bigNumberA.length() % 2 != 0) {
  40.             bigNumberA = "0" + bigNumberA;
  41.         }
  42.         a = bigNumberA.substring(0, bigNumberA.length() / 2);
  43.         b = bigNumberA.substring(bigNumberA.length() / 2);
  44.     }
  45.     if (bigNumberB.length() == 1) {
  46.         c = "0";
  47.         d = bigNumberB;
  48.     } else {
  49.         if (bigNumberB.length() % 2 != 0) {
  50.             bigNumberB = "0" + bigNumberB;
  51.         }
  52.         c = bigNumberB.substring(0, bigNumberB.length() / 2);
  53.         d = bigNumberB.substring(bigNumberB.length() / 2);
  54.     }
  55.     // 按最大位数取值，以确定补零数目
  56.     int n = bigNumberA.length() >= bigNumberB.length() ? bigNumberA.length() : bigNumberB.length();

  58.     //t1,t2为中间运算结果，t3为乘法运算完毕的结果
  59.     String t1, t2, t3;
  60.     String ac = bigNumberMultiply(a, c);
  61.     String bd = bigNumberMultiply(b, d);

  63.     //t1=(A-B)(D-C)
  64.     t1 = bigNumberMultiply(bigNumberSubtract(a, b), bigNumberSubtract(d, c));
  65.     //t2=(A-B)(D-C)+AC+BD
  66.     t2 = bigNumberSum(bigNumberSum(t1, ac), bd);
  67.     //t3= AC * 10^n+((A-B)(D-C)+AC+BD) * 10^(n/2)+BD
  68.     t3 = bigNumberSum(bigNumberSum(Power10(ac, n), Power10(t2, n/2)), bd).replaceAll("^0+", "");
  69.     if (t3 == "")
  70.         return "0";
  71.     if(isNegative){
  72.         return "-" + t3;
  73.     }
  74.     return t3;
  75. }


  79. /**
  80.  * 大整数加法
  81.  * @param bigNumberA  大整数A
  82.  * @param bigNumberB  大整数B
  83.  */
  84. public static String bigNumberSum(String bigNumberA, String bigNumberB) {

  86.     if (bigNumberA.startsWith("-") && !bigNumberB.startsWith("-")) {
  87.         return bigNumberSubtract(bigNumberB, bigNumberA.replaceAll("^-", ""));
  88.     } else if (!bigNumberA.startsWith("-") && bigNumberB.startsWith("-")) {
  89.         return bigNumberSubtract(bigNumberA, bigNumberB.replaceAll("^-", ""));
  90.     } else if (bigNumberA.startsWith("-") && bigNumberB.startsWith("-")) {
  91.         return "-" + bigNumberSum(bigNumberA.replaceAll("^-", ""), bigNumberB.replaceAll("^-", ""));
  92.     }

  94.     //1.把两个大整数用数组逆序存储，数组长度等于较大整数位数+1
  95.     int maxLength = bigNumberA.length() > bigNumberB.length() ? bigNumberA.length() : bigNumberB.length();
  96.     int[] arrayA = new int[maxLength+1];
  97.     for(int i=0; i< bigNumberA.length(); i++){
  98.         arrayA[i] = bigNumberA.charAt(bigNumberA.length()-1-i) - '0';
  99.     }
  100.     int[] arrayB = new int[maxLength+1];
  101.     for(int i=0; i< bigNumberB.length(); i++){
  102.         arrayB[i] = bigNumberB.charAt(bigNumberB.length()-1-i) - '0';
  103.     }
  104.     //2.构建result数组，数组长度等于较大整数位数+1
  105.     int[] result = new int[maxLength+1];
  106.     //3.遍历数组，按位相加
  107.     for(int i=0; i
  108.         int temp = result[i];
  109.         temp += arrayA[i];
  110.         temp += arrayB[i];
  111.         //判断是否进位
  112.         if(temp >= 10){
  113.             temp -= 10;
  114.             result[i+1] = 1;
  115.         }
  116.         result[i] = temp;
  117.     }
  118.     //4.把result数组再次逆序并转成String
  119.     StringBuilder sb = new StringBuilder();
  120.     //是否找到大整数的最高有效位
  121.     boolean findFirst = false;
  122.     for (int i = result.length - 1; i >= 0; i--) {
  123.         if(!findFirst){
  124.             if(result[i] == 0){
  125.                 continue;
  126.             }
  127.             findFirst = true;
  128.         }
  129.         sb.append(result[i]);
  130.     }
  131.     return sb.toString();
  132. }

  135. /**
  136.  * 大整数减法
  137.  * @param bigNumberA  大整数A
  138.  * @param bigNumberB  大整数B
  139.  */
  140. public static String bigNumberSubtract(String bigNumberA, String bigNumberB) {
  141.     int compareResult = compare(bigNumberA, bigNumberB);
  142.     if (compareResult == 0) {
  143.         return "0";
  144.     }
  145.     boolean isNegative = false;
  146.     if (compareResult == -1) {
  147.         String tmp = bigNumberB;
  148.         bigNumberB = bigNumberA;
  149.         bigNumberA = tmp;
  150.         isNegative = true;
  151.     }
  152.     //1.把两个大整数用数组逆序存储，数组长度等于较大整数位数+1
  153.     int maxLength = bigNumberA.length() > bigNumberB.length() ? bigNumberA.length() : bigNumberB.length();
  154.     int[] arrayA = new int[maxLength+1];
  155.     for(int i=0; i< bigNumberA.length(); i++){
  156.         arrayA[i] = bigNumberA.charAt(bigNumberA.length()-1-i) - '0';
  157.     }
  158.     int[] arrayB = new int[maxLength+1];
  159.     for(int i=0; i< bigNumberB.length(); i++){
  160.         arrayB[i] = bigNumberB.charAt(bigNumberB.length()-1-i) - '0';
  161.     }
  162.     //2.构建result数组，数组长度等于较大整数位数+1
  163.     int[] result = new int[maxLength+1];
  164.     //3.遍历数组，按位相加
  165.     for(int i=0; i
  166.         int temp = result[i];
  167.         temp += arrayA[i];
  168.         temp -= arrayB[i];
  169.         //判断是否进位
  170.         if(temp < 0){
  171.             temp += 10;
  172.             result[i+1] = -1;
  173.         }
  174.         result[i] = temp;
  175.     }
  176.     //4.把result数组再次逆序并转成String
  177.     StringBuilder sb = new StringBuilder();
  178.     //是否找到大整数的最高有效位
  179.     boolean findFirst = false;
  180.     for (int i = result.length - 1; i >= 0; i--) {
  181.         if(!findFirst){
  182.             if(result[i] == 0){
  183.                 continue;
  184.             }
  185.             findFirst = true;
  186.         }
  187.         sb.append(result[i]);
  188.     }
  189.     String value = sb.toString();
  190.     if (isNegative) {
  191.         value = "-" + value;
  192.     }
  193.     return value;
  194. }

  197. // 比较大小
  198. private static int compare(String x, String y) {
  199.     if (x.length() > y.length()) {
  200.         return 1;
  201.     } else if (x.length() < y.length()) {
  202.         return -1;
  203.     } else {
  204.         for (int i = 0; i < x.length(); i++) {
  205.             if (x.charAt(i) > y.charAt(i)) {
  206.                 return 1;
  207.             } else if (x.charAt(i) < y.charAt(i)) {
  208.                 return -1;
  209.             }
  210.         }
  211.         return 0;
  212.     }
  213. }

  216. // 扩大10的n次方倍
  217. public static String Power10(String num, int n) {
  218.     for (int i = 0; i < n; i++) {
  219.         num += "0";
  220.     }
  221.     return num;
  222. }

  225. public static void main(String[] args) {
  226.     String x = "1513143";
  227.     String y = "9345963";
  228.     System.out.println(bigNumberMultiply(x, y));
  229. }
 
 

 
 
需要注意的是，这段实现代码只适用于两个大整数长度相等的情况。如果想求解长度不等的整数相乘，只需要对代码做微小的改动，有兴趣的小伙伴没有试一试。
 
 

 
 
640?wx_fmt=jpeg
 
 

 
 
640?wx_fmt=jpeg
 
 

 
 
640?wx_fmt=jpeg
 
 

 
 
640?wx_fmt=jpeg
 
 

 
 
640?wx_fmt=jpeg
 
 

 
 

 
 
640?wx_fmt=jpeg
 
 

 
 
文章转自程序员小灰
 
 

 
 
1.微信群：
 
 
添加小编微信：color_ld，备注“进群+姓名+公司职位”即可，加入【云计算学习交流群】，和志同道合的朋友们共同打卡学习！
 
 

 
 
2.征稿：
 
 
投稿邮箱：[email protected]；微信号：color_ld。请备注投稿+姓名+公司职位。
 
 

 
 
推荐阅读
 
  
 

 
 
程序员抢票姿势 ↓交朋友还能抢票？
 
 

 
 
640?wx_fmt=jpeg
 
 
为交流学习，请备注+姓名+公司职位（学校专业）
 
 

 
 
640?wx_fmt=gif点击“阅读原文”，打开 CSDN App 阅读更贴心！
 


                

        

        
    

                

                

                    注：本文转载自blog.csdn.net的CSDN云计算的文章"https://blog.csdn.net/FL63Zv9Zou86950w/article/details/85501493"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
                

                

                    

                        

                            

                                
                                
                                
                                
                                    
                                
                                
                                
                                
                                
                                
                                
                                
                                
                                
                                

                                    复制链接
                                    
                                

                                

                                    
                                    

                                        

                                            

                                        

                                    

                                

                            

                        

                    

                


                

                    





                        
                    

                

                

                
            



            

            

                
相关推荐

                

                    

                    

                

            

            

                

                    

                        

							
								发表评论
                        

                        
                    

                    

                        

                            

								
                            

                            

                                

                                    

                                        
                                    

                                    

                                        
                                    

                                

                            

                            

                                
                            

                        

                        
评论记录：

                        
                        
                        
                        
                        
                        
未查询到任何数据！