计算超大整数的阶乘（java）

你的名字 2022-05-15 07:54 217阅读 0赞

## 思想 ##

> 思想来自于网上，将所有的计算结果每一位存储到数组中，利用十进制，每次阶乘对数组中的每一位与目标阶乘，然后计算进位，比如：8！= 5040\*8=\{5,0,4,0\}\*8=\{40,0,32,0\}=\{4,0,3,2,0\}

## 代码实现 ##

/** * 计算大整数的阶乘 * @param bigNumber */
        public static void getBigFactorial(long bigNumber){
    
            if (bigNumber<0){
                throw new IllegalArgumentException("参数必须为非负数");
            }
            //数组长度
            double length =0;
            //总位数
            int count = 0;
            //记录最高位
            int maxIndex = 0;
    
            //计算最终数组的长度
            for (int i=1;i<= bigNumber;i++){
                length += Math.log10(i);
            }
            //最终结果数组，结果按照倒序存放
            long[] result = new long[(int)length+1];
    
            result[0]=1;
            for (int i=1;i<=bigNumber;i++){
    
                //获取最高位下标位置
                maxIndex = getMaxIndex(result);
    
                //从个位开始向后计算每一位的结果
                for (int j=0;j<=maxIndex;j++){
                    result[j]*=i;
                }
                //a为进位数
                long a = 0;
                //将数组进位
                for (int j=0;j<=maxIndex;j++){
                    //当前位加上进位
                    result[j]+=a;
                    if (result[j]<=9){
                        //下一位不需要进位
                        a=0;
                    }else  if (result[j]>9 && j<maxIndex){
                        //记录进位
                        a = result[j]/10;
                        //当前位
                        result[j]%=10;
                    }else if (result[j]>9&&j>=maxIndex){
    
                        //最高位，循环进位
                        while (result[j]>9){
                            a = result[j]/10;
                            result[j]=result[j]%10;
                            //最高位保留进位
                            result[++j]=a;
                        }
                    }
                }
            }
    
            int zeroCount = 0;
            for (int i=result.length-1;i>=0;i--){
    
                count++;
                if (result[i] == 0){
                    zeroCount++;
                }else {
                    zeroCount = 0;
                }
                System.out.print(result[i]);
    
                if (count%40==0) {
                    System.out.println();
                }else if (count%5==0){
                    System.out.print(" ");
                }
            }
    
            System.out.println("\n计算结束，总位数："+count+"\t 末尾0的个数："+zeroCount);
    
        }
    
        /** * 获取数组最高位下标位置 * @param arr * @return */
        private static int getMaxIndex(long[] arr){
    
            for (int i=arr.length-1;i>=0;i--){
                if (arr[i]!=0){
                    return i;
                }
            }
            return 0;
        }

## 测试结果 ##

public static void main(String[] args) {
            long start = System.currentTimeMillis();
            getBigFactorial(1000);
            long end = System.currentTimeMillis();
            System.out.println("计算用时: "+(end-start)+" ms");
        }

--------------------

40238 72600 77093 77354 37024 33923 00398 57193
    74864 21071 46325 43799 91042 99385 12398 62902
    05920 44208 48696 94048 00479 98861 01971 96058
    63166 68729 94808 55890 13238 29669 94459 09974
    24504 08707 37599 18823 62772 71887 32519 77950
    59509 95276 12087 49754 62497 04360 14182 78094
    64649 62910 56393 88743 78864 87337 11918 10458
    25783 64784 99770 12476 63288 98359 55735 43251
    31853 23958 46307 55574 09114 26241 74743 49347
    55342 86465 76611 66779 73966 68820 29120 73791
    43853 71958 82498 08126 86783 83745 59731 74613
    60853 79534 52422 15865 93201 92809 08782 97308
    43139 28444 03281 23155 86110 36976 80135 73042
    16168 74760 96758 71348 31202 54785 89320 76716
    91324 48426 23613 14125 08780 20800 02616 83151
    02734 18279 77704 78463 58681 70164 36502 41536
    91398 28126 48102 13092 76124 48963 59928 70511
    49649 75419 90934 22215 66832 57208 08213 33186
    11681 15536 15836 54698 40467 08975 60290 09505
    37616 47584 77284 21889 67964 62449 45160 76535
    34081 98901 38544 24879 84959 95331 91017 23355
    55660 21394 50399 73628 07501 37837 61530 71277
    61926 84903 43526 25200 01588 85351 47331 61170
    21039 68175 92151 09077 88019 39317 81141 94545
    25722 38655 41461 06289 21879 60223 83897 14760
    88506 27686 29671 46674 69756 29112 34082 43920
    81601 53780 88989 39645 18263 24367 16167 62179
    16890 97799 11903 75403 12746 22289 98800 51954
    44414 28201 21873 61745 99264 29565 81746 62830
    29555 70299 02432 41531 81617 21046 58320 36786
    90611 72601 58783 52075 15162 84225 54026 51704
    83304 22614 39742 86933 06169 08979 68482 59012
    54583 27168 22645 80665 26769 95865 26822 72807
    07578 13918 58178 88965 22081 64348 34482 59932
    66043 36766 01769 99612 83186 07883 86150 27946
    59551 31156 55203 60939 88180 61213 85586 00301
    43569 45272 24206 34463 17974 60594 68257 31037
    90084 02443 24384 65657 24501 44028 21885 25247
    09351 90620 92902 31364 93273 49756 55139 58720
    55965 42287 49774 01141 33469 62715 42284 58623
    77387 53823 04838 65688 97646 19273 83814 90014
    07673 10446 64025 98994 90222 22176 59043 39901
    88601 85665 26485 06179 97023 56193 89701 78600
    40811 88972 99183 11021 17122 98459 01641 92106
    88843 87121 85564 61249 60798 72290 85192 96819
    37238 86426 14839 65738 22911 23125 02418 66493
    53143 97013 74285 31926 64987 53372 18940 69428
    14341 18520 15801 41233 44828 01505 13996 94290
    15348 30776 44569 09907 31524 33278 28826 98646
    02789 86432 11390 83506 21709 50025 97389 86355
    42771 96742 82224 87575 86765 75234 42202 07573
    63056 94988 25087 96892 81627 53848 86339 69099
    59826 28095 61214 50994 87170 12445 16461 26037
    90293 09120 88908 69420 28510 64018 21543 99457
    15680 59418 72748 99809 42547 42173 58240 10636
    77404 59574 17851 60829 23013 53580 81840 09699
    63725 24230 56085 59037 00624 27124 34169 09004
    15369 01059 33983 83577 79394 10970 02775 34720
    00000 00000 00000 00000 00000 00000 00000 00000
    00000 00000 00000 00000 00000 00000 00000 00000
    00000 00000 00000 00000 00000 00000 00000 00000
    00000 00000 00000 00000 00000 00000 00000 00000
    00000 00000 00000 00000 00000 00000 00000 00000
    00000 00000 00000 00000 00000 00000 00000 00000
    00000 000
    计算结束，总位数：2568    末尾0的个数：249
    计算用时: 25 ms