50000的阶乘

请了个长假回学校弄毕业，公司发来第二季度的编程习题，这才发现公司原来还有个这么有趣的活动，题目的要求是计算一个数的阶乘，然后将结果的各位数字求和输出。

求阶乘挺简单的，不过题目要求能计算1~50000的阶乘，50000的阶乘难以想象，显然太大了。用java做，因为公司主要用java做开发，这道题规定了不能用BigDecimal啥的，那就自己写大数相乘的吧。。50000的阶乘要求在10分钟以内。。说明确实有点麻烦。

开写，首先先初始化结果数组，用的int[]，多长呢？我估计了一下，50000的阶乘长度肯定小于50000的50000次方的长度，肯定小于100000的50000次方的长度，于是肯定小于250000，于是就初始化了int[250000]数组result，没有办法。。。然后初始化第一个原素为1，然后递归，c语言递归很容易溢出，java递归我还没遇到过，试试看看情况。发现还需要再创建一个临时数组，用于存放一次乘法的结果，于是又加了一个int[250000]的temp数组，因为乘法需要把被乘数各位与乘数求积，然后将结果按位累加，累加的结果保存到临时数组里，然后算完了复制到结果数组，供下次继续计算。

然后算一算，发现算到3100多的阶乘时，报java.lang.StackOverflowError，汗。。经鉴定，java递归果然也是会栈溢出的。。似乎比c语言递归得多几轮。可是我还意犹未尽，心想把阶乘结果末位0去了看看，于是在复制temp数组到result的过程中，忽略了末位的0，果然结果长度大减少，这下计算到3800多的阶乘时才溢出，说明和c语言一样栈溢出都与递归体占用内存大小有关的。

改成循环，接着来，算阶乘着实有点麻烦，还没算完50000，我等不及了，心想会不会有什么公式规律什么的快速计算阶乘结果和各位和，记得以前做ACM做过类似的题，于是我尝试在做乘法前先算出被乘数的各位和，再把这个和与乘数相乘，后来我证明了半天，发现这个方法确实不行，只能证明乘数与被乘数先各位求和后再相乘的结果的各位和继续求和，求出的最终的个位数的各位和与原结果的各位和求出的个位数的各位和是相同的，比如9!=362880，结果各位和为27，27的各位和为9，最终求出的个位数的各位和与先算出的各位和是相同的，说得有些拗口，算了，再多嘴一下，其实6!以后，所有结果这么算下去各位和都是9，原因不解释了。。9乘任何数以后的结果这么算各位和都是9….

尔后又尝试了各种方案，发现都不大好用，于是老实算50000的阶乘，囧啊。然后真算出来了，发现去除末尾的0，结果长度为200738，然后我把长度改为201000。然后很惊讶的发现时间果然是10分钟多一点儿。。看来题目要求不是乱出的。。。然后想办法调一调吧，尝试了一下从大到小算阶乘，发现速度还比不上从小到大的来；然后在去除结果末位0的时候，感觉能不能把结果当中的0去掉，因为最后要算各位和嘛，中间结果里中间的0乘出来还是0嘛。然后又仔细论证了一下，发现不是这样子的，在算结果时会出现损失，因为两数加的进位可能会占用中间结果的0，如果忽略这些0，于是就出错了。。解释得不大清楚，直接地说吧，去除0之后，和之前的情况一样，只有算最终的个位数的各位和才能和不去0结果一样。只算阶乘结果的各位和，必须要把最终的阶乘结果算出来。

那就接着优化吧，201000长度的数组，复制结果估计特别费时，于是我想了个不需要复制结果的方法，用两个数组，轮流保存结果与临时结果。为了程序显得高级，我用了个2维数组data，初始化int[2][201000]，使data[0][0] = 1，用flag=0标识当前结果数组为data[0][]，也就是data[flag][]，一次计算后切换数组时，只要flag^=1就可以了^_^。我满怀信心地测试这个程序，先用10000试了下，发现还真快了几秒钟，快了10%的样子，可是测试50000时惊讶的发现，速度反而慢了。。。真是让人心寒，又多试了两遍，发现真的变慢了，好囧啊~，当然也有可能是电脑正在执行别的操作的原因，不过这样可以得出一个结论，复制大数组的数据对这个程序时间上影响不大，就是说时间主要还是消耗在了乘法结果累加上，我觉得主要是因为大数组数据存取时的寻址操作占用了大量时间。毕竟每次执行result[i]，JVM都要到内存中找i下标指向的内存空间，写的时候不注意，i很大的话，这个调用还是蛮费时间的。我在优化时将result[i]的调用都尽量减少，争取只读一次、只写一次，不重复读取。如果能像c/c++那样使用指针就好了，这样可以在读取时只寻址一次，然后写数据用指针操作估计能减少不少时间。

最后很遗憾，程序优化不起来，感觉再优化的话就要使用一些不登大雅之堂的方法了。考虑了一种方法，我们可以事先保存一些阶乘的结果，例如20000!、30000!、35000!、40000!…在计算时，根据要求计算的数大小，选择已有的起始结果，继续做乘法，这样岂不是快了很多。毕竟算阶乘时从1开始做乘法，就默认了1是起始数，我们也可以从2开始（若要求计算1、2，则直接输出），同样，为啥不可以先初始化各种数值范围的起始结果呢？但这样的话，直接把1~50000的阶乘结果全保存下来，直接各要求输出结果岂不是更爽，反正就50000个数而已。。。话说，要是为了速度，就不应该使用面向对象的编程思想，更不该用这种面向对象的语言了，毕竟方法调来调去，意味着要不停地寻址，找call的入口，多麻烦啊~
最后附两个代码：

这个程序算50000时，离10分钟就差10几秒了。。

package com.thunisoft.exercise.y2012q2;
import java.util.Date;

/**
 * @author XuDing
 * @date 2012-06-29
 *
 */
public class FactorialO {
 int LENGTH = 201000; //经鉴定，去末尾0后长度小于这个
 int[] result = new int[LENGTH];
 int[] temp = new int[LENGTH];
 int rLength = 1;  //结果数组实际长度，数组最大下标值+1
 int tLength = 0;  //临时数组实际长度
 long start = new Date().getTime();
 
 public static void main(String[] args) {
  FactorialO f = new FactorialO();
  f.init();
  int n = 0;
  try {
   n = Integer.parseInt(args[0]);
  } catch (Exception e) {
   System.out.println(""参数不正确！"");
  }
  f.calc(n);
  f.output();
 }

 private void output() {
  int num = 0;
  for(int i=0;i<rLength;i++){
   num+=result[i];
  }
  System.out.println(""徐丁:"" + (new Date().getTime() - start) + "":"" + num);
 }

 public void init() {
  result[0] = 1;
 }
 
 private void calc(int n) {
  int m = 2;
  if(m>n||n==1)
   return;
  for (;m<=n;m++) {
   for(int i=0;i<rLength;i++) {
    addToTemp(result[i]*m, i);
   }
   copyTempToResult();
  }
//  while(n>1){  //实践表明还是正序来得快
//   for(int i=0;i<rLength;i++) {
//    addToTemp(result[i]*n, i);
//   }
//   n--;
//   copyTempToResult();
//  }
 }
 
 private void copyTempToResult() {
  int b = 0;
  int i = 0;
  while(temp[i]==0){  //去掉后面的0
   i++;
  }
  for(;i<tLength;i++){
   result[b++] = temp[i];
   temp[i] = 0;
   rLength = b;
  }
 }

 private void addToTemp(int r, int b) {
  int f = 0;
  do{
   int t = temp[b] + r%10;
   if(t > 9){
    temp[b+1]+=1;
    t-=10;
    if(r < 10) //此时最高位进位
     f = 1;
   }
   temp[b] = t;
   b++;
  }while((r/=10)!=0);
  tLength = b + f; //最高位有进位，长度须加1
 }
}

这是不复制临时数组，交替使用数组的程序，稍微短点

package com.thunisoft.exercise.y2012q2;

import java.util.Date;

/**
 * @author XuDing
 * @date 2012-06-29
 *
 */
public class Factorial {
 int LENGTH = 201000; //经鉴定，去末尾0后长度小于这个
 int[][] data = new int[2][LENGTH];
 int flag = 0;
 int rLength = 1;  //结果数组实际长度，数组最大下标值+1
 int tLength = 0;  //临时数组实际长度
 long start = new Date().getTime();
 
 public static void main(String[] args) {
  Factorial f = new Factorial();
  f.init();
  int n = 0;
  try {
   n = Integer.parseInt(args[0]);
  } catch (Exception e) {
   System.out.println(""参数不正确！"");
  }
  f.calc(n);
  f.output();
 }

 private void output() {
  int num = 0;
  for(int i=0;i<rLength;i++){
   num+=data[flag][i];
  }
  System.out.println(""徐丁:"" + (new Date().getTime() - start) + "":"" + num);
 }

 public void init() {
  data[0][0] = 1;
 }
 
 private void calc(int n) {
  int m = 2;
  if(m>n||n==1)
   return;
  for (;m<=n;m++) {
   int b = 0;  //记录结果起始位
   int i = 0;
   while(i<rLength){  //去除结尾的0，减小结果长度
    if(data[flag][i]!=0)
     break;
    i++;
   }
   for(;i<rLength;i++) {
    addToTemp(data[flag][i]*m, b++);
    data[flag][i] = 0;  //置为原存储区为0，作为下一轮计算时的临时存储区
   }
   flag^=1;
   rLength = tLength;
  }
 }

 private void addToTemp(int r, int b) {
  int f = 0;
  do{
   int t = data[flag^1][b] + r%10;
   if(t > 9){
    data[flag^1][b+1]+=1;
    t-=10;
    if(r < 10) //此时最高位进位
     f = 1;
   }
   data[flag^1][b] = t;
   b++;
  }while((r/=10)!=0);
  tLength = b + f; //最高位有进位，长度须加1
 }

}