Java中超大整数阶乘算法的示例分析

这篇文章给大家分享的是有关Java中超大整数阶乘算法的示例分析的内容。小编觉得挺实用的，因此分享给大家做个参考，一起跟随小编过来看看吧。

这个方法采用"数组进位"算法。在超越计算机变量取值范围的情况下，将多位数相乘转化为一位数相乘。如11！=39916800，若需求12的阶乘，则需要将39916800与12相乘，可利用乘法分配率。乘法竖式如下图所示：

使用一个数组来保存阶乘每一位的结果，一个数组元素保存一位数。例如：将11的阶乘的结果399
16800保存到数组的8个元素中，要计算12的阶乘就用每个数组元素中的值去乘以12，并将结果保存到原来的数组元素中。接下来去判断每个数组元素是否需要进位，通过进位操作使数组中的每个元素保存的数都只有一位数，示意图如下：

理论上讲，只要计算机内存空间允许就可以保存任意多位的阶乘结果，不再受变量的取值范围的限制，只受到操作系统的寻址能力和计算机内存的限制。友情提示：如果要求的阶乘数字很大则可以将数组定义为long类型，以避免在计算单位数的乘积时出现溢出的情况。

实现代码如下：

public class BigInteger {        /**         * 计算进位         * @param bit     数组         * @param pos 用于判断是否是数组的最高位         */        private void carry(int[] bit, int pos)                {                int i ,carray = 0;                for (i = 0 ; i<= pos ;i++)//从0到pos逐位检查是否需要进位                {                        bit[i] += carray;                        //累加进位                        if(bit[i] <= 9)     //小于9不进位                        {                                carray = 0;                        } else if(bit[i] >9 && i 9 && i >= pos)//大于9，且是最高位                        {                                while(bit[i] > 9)//循环向前进位                                {                                        carray = bit[i]/10;                                        //计算进位值                                        bit[i] = bit[i] % 10;                                        //当前的第一位数                                        i ++ ;                                        bit[i] = carray;                                        //在下一位保存进位值                                }                        }                }        }        /**         * 大整数阶乘         * @param bigInteger 所计算的大整数         */        private void bigFactorial(int bigInteger)                {                int pos =0;                //                int digit;                //数据长度                int a , b ;                int m = 0 ;                //统计输出位数                int n = 0 ;                //统计输出行数                double sum = 0;                //阶乘位数                for (a = 1 ; a <= bigInteger ; a ++)//计算阶乘位数                {                        sum += Math.log10(a);                }                digit = (int)sum + 1;                //数据长度                int[] fact = new int[digit];                //初始化一个数组                 fact[0] = 1;                //设个位为 1                for (a = 2 ; a <= bigInteger ; a++ )//将2^bigInteger逐个与原来的积相乘                {                        for (b = digit-1 ; b >= 0 ; b--)//查找最高位{}                         {                                if( fact[b] != 0 )                                                                {                                        pos = b ;                                        //记录最高位                                        break;                                }                        }                        for (b = 0; b <= pos ; b++)                                                {                                fact[b] *= a ;                                //每一位与i乘                        }                        carry(fact,pos);                }                for (b = digit-1 ; b >= 0 ; b --)                                {                        if(fact[b] != 0)                                                {                                pos = b ;                                //记录最高位                                 break;                        }                }                System.out.println(bigInteger +"阶乘结果为：");                for (a = pos ; a >= 0 ; a --)//输出计算结果                {                        System.out.print(fact[a]);                        m++;                        if(m % 5 == 0)                                                {                                System.out.print(" ");                        }                        if(40 == m )                                                {                                System.out.println("");                                m = 0 ;                                n ++;                                if(10 == n )                                                                {                                        System.out.print("\n");                                        n = 0;                                }                        }                }                System.out.println("\n"+"阶乘共有: "+(pos+1)+" 位");        }        public void doBigFactorial(int bigInteger)                {                int timeBegin=(int) System.currentTimeMillis();                this.bigFactorial(bigInteger);                int timeFinishi=(int) System.currentTimeMillis();                int time = timeFinishi-timeBegin;                System.out.println("计算耗时: " + time +"毫秒" );        }        public static void main(String[] args)                {                BigInteger bi = new BigInteger();                bi.doBigFactorial(100000);        }}

计算10,0000的阶乘，显示结果如下：

这样的结果，控制台显然已经无法保存内容了。10万的阶乘有45万位之多，这就相当于一本有45万字的小说一样。对比1000的阶乘结果如下：

控制台可以完整显示。

感谢各位的阅读！关于"Java中超大整数阶乘算法的示例分析"这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，让大家可以学到更多知识，如果觉得文章不错，可以把它分享出去让更多的人看到吧！