较大数字的乘法

淡淡的烟草味﹌ 2023-10-03 08:26 12阅读 0赞

#### 目录 ####

*  前言
 *  计算过程

## 前言 ##

在知乎上，刷到过比较搞笑的话题：比较2个数的大小：45321 与 54321 ；一般正常的做法是两边取对数，再计算对数的大小；这样就能把这2个很大的数转换成较小的数，然后利用计算器就搞定了。但是呢，总有很沙雕的答案===>直接把45321 与 54321 结果算出来比大小。

45321 与 54321 这2个数字的长度都很长用long，BigDecimal是不行的，只能用原始的方法了。首先这2个数的幂都很大，如果直接for循环效率可能不高，这个可以利用指数的性质：（ab)n = abn ，减少运算的次数。  
  比如：4 10 = (42)5 =165 = 16 \* (162)2 = 16 \* 2562 =16 \* 65536=1048576；可以看出，当指数越大这样计算得效果就越好。但是也有一个问题，当指数越来越大，底数就越来越大；最后底数大小超过数据类型大小限制就无法进行有效计算了。所以当2个大数相乘时，只能利用小学学过的竖式计算了。但是得稍微改变下计算得过程；

总结一下，当遇到这种超大指数得运算时会遇到的问题：

*  指数太大，如果直接for循环效率会比较低；这个时候需要利用指数运算得规则来减少计算次数；
 *  当参与运算得数据超过数字存储得内存时，就不能直接利用2个数相乘了。需要将数字存储到数组中利用竖式计算得原理来计算值。

## 计算过程 ##

上面讲到当2个大数相乘时，只能用需要稍微改进一下：

![在这里插入图片描述][2374fcb88b334133afa2ff6b3eff565f.png_pic_center]

我们手写计算过程时，是每计算一个数字都直接进位，到但是这样直接处理代码很麻烦；先各个部分相乘，对齐相加，最后处理进位，这样处理比较简单。

代码：

/**
         *
         *
         * 快速幂
         *
         * @param a  底数
         * @param n  指数
         * @return
         */
        static int[] factorial(int a,int n){
        
            int[] odd_n_del = new int[10];
            odd_n_del[0]=1;
            int[] base = initVal(a);//将底数转换成数组形式：478 ===>{8,7,4}
            while(n>1){
        
                if((n&1) !=0){
        
                    odd_n_del = mul(odd_n_del,base);
                }
                base = mul(base,base);
                n/=2;
            }
    
            return mul(base,odd_n_del);
        }
    
    
       static int[] initVal(int a){
        
           return initVal(a+"");
        }
        //将底数转换成数组形式：478 ===>{8,7,4}
        static int[] initVal(String a){
        
            char[] chars = a.toCharArray();
            int[]res = new int[chars.length];
            for (int i = chars.length - 1, j=0; i >= 0; i--,j++) {
        
                res[j] = Integer.parseInt(chars[i]+"");
            }
            return res;
        }
    
    
    
        /**
         *
         *
         * @param res 数据
         * @param wrap 换行
         * @return
         */
    
        static int[] mul(int[] a, int[] b){
        
    
            int al = getHighIndex(a);//a_length
            int bl = getHighIndex(b);//b_length
    
            int []res = new int[al+bl+4];
    
            for (int i = 0; i <=al ; i++) {
        
    
                for (int j = 0; j <= bl; j++) {
        
    
                    res[i+j] += a[i] * b[j];
                }
    
            }
    
            //处理最后的计算结果；res[i]中只保留个位数， res[i] /10是进位；
            for (int i = 0; i < res.length-1; i++) {
        
                int temp = res[i];
                res[i] = temp%10;
                res[i+1] = temp/10+res[i+1];
            }
    
            return res;
        }
    
        /**
         *
         * 获取数组最高位的下标
         * @param arr
         * @return
         */
        static int getHighIndex(int[] arr){
        
            for (int i = arr.length - 1; i >= 0; i--) {
        
                if(arr[i]!=0)return i;
            }
            return -1;
        }

测试：

/**
         * @param res 数据
         * @param wrap 控制一行打印字符数
         * @return
         */
        String toString(int[]res,int wrap){
        
            int high_index = getHighIndex(res);
            System.out.println("数字长度："+(high_index+1));
    
            StringBuilder num = new StringBuilder("");
            int split = 0;
            for (int i =high_index; i >= 0; i--) {
        
                split++;
                if(split%wrap == 0)
                    num.append(res[i]+"\n");
                else
                    num.append(res[i]);
            }
            return num.toString();
        }
    
    
        @Test
        public void test2(){
        
    
            int[] res = factorial(4,5321);
    //        System.out.println("len:"+res.length);
            System.out.println(toString(res,100));
    
        }

[2374fcb88b334133afa2ff6b3eff565f.png_pic_center]: https://img-blog.csdnimg.cn/2374fcb88b334133afa2ff6b3eff565f.png#pic_center