Java版超大整数阶乘算法-10,0000级

绝地灬酷狼 2022-06-18 07:06 142阅读 0赞

原帖地址：     http://www.open-open.com/home/space-135360-do-blog-id-9620.html

当计算超过20以上的阶乘时，阶乘的结果值往往会很大。一个很小的数字的阶乘结果就可能超过目前个人计算机的整数范围。如果需求很大的阶乘，比如1000以上完全无法用简单的递归方式去解决。在网上我看到很多用C、C++和C\#写的一些关于大整数阶乘的算法，其中不乏经典但也有很多粗糙的文章。数组越界，一眼就可以看出程序本身无法运行。转载他人文章的时候，代码倒是仔细看看啊。唉，粗糙。过年了，在家闲来蛋疼，仔细分析分析，用Java实现了一个程序计算超大整数阶乘。思想取自网上，由我个人优化和改进。

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

![20130208071023_27594.png][]  
【乘法竖式图】

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

![20130208072128_62962.png][]  
【进位示意图】

理论上讲，只要计算机内存空间允许就可以保存任意多位的阶乘结果，不再受变量的取值范围的限制，只受到操作系统的寻址能力和计算机内存的限制。友情提示：如果要求的阶乘数字很大则可以将数组定义为 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<pos)//大于9，但不是最高位
    			{
    				carray = bit[i]/10;//保存进位值
    				bit[i] = bit[i]%10;//得到该位的一位数
    			}
    			else if(bit[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的阶乘，显示结果如下：

![20130208073656_59943.png][]

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

![20130208074014_86934.png][]

控制台可以完整显示。

[20130208071023_27594.png]: /images/20220618/d61e0ee3e4fa428caed0518e7bc0abce.png
[20130208072128_62962.png]: /images/20220618/8eac6e1dc9c94cf289d90e623e5dfda8.png
[20130208073656_59943.png]: /images/20220618/d6e784b5b5f44dc49d8eb0d85d015960.png
[20130208074014_86934.png]: /images/20220618/a6d456c649ca422e8363f43ff1d0c9ca.png