WV.21-大数阶乘算法1-序

序

大数阶乘的计算是一个有趣的话题，从中学生到大学教授，许多人都投入到这个问题的探索和研究之中，并发表了他们自己的研究成果。如果你用阶乘作关键字在google上搜索，会找到许多此类文章，另外，如果你使用google学术搜索，也能找到一些计算大数阶乘的学术论文。但这些文章和论文的深度有限，并没有给出一个高速的算法和程序。

?

我和许多对大数阶乘感兴趣的人一样，很早就开始编制大数阶乘的程序。从2000年开始写第一个大数阶乘程序算起，到现在大约己有6-7年的时光，期间我写了多个版本的阶乘计算器，在阶乘计算器的算法探讨和程序的编写和优化上，我花费了很大的时间和精力，品尝了这一过程中的种种甘苦，我曾因一个新算法的实现而带来速度的提升而兴奋，也曾因费了九牛二虎之力但速度反而不及旧的版本而懊恼，也有过因解一个bug而通宵敖夜的情形。我写的大数阶乘的一些代码片段散见于互联网络，而算法和构想则常常萦绕在我的脑海。自以为，我对大数阶乘计算器的算法探索在深度和广度上均居于先进水平。我常常想，应该写一个关于大数阶乘计算的系列文章，一为整理自己的劳动成果，更重要的是可以让同行分享我的知识和经验，也算为IT界做一点儿贡献吧。

　 我的第一个大数阶乘计算器始于2000年，那年夏天，我买了一台电脑，开始在家专心学习VC，同时写了我的第一个VC程序，一个仿制windows界面的计算器。该计算器的特点是高精度和高速度，它可以将四则运算的结果精确到6万位以内，将三角、对数和指数函数的结果精确到300位以内，也可以计算开方和阶乘等。当时，我碰巧看到一个叫做实用计器的软件。值得称颂的是，该计算器的作者姜边竟是一个高中生，他的这个计算器功能强大，获得了各方很高的评价。该计算的功能之一是可以计算9000以内阶乘的精确值，且速度很快。在佩服之余，也激起我写一个更好更快的程序的决心，经过几次改进，终于使我的计算器在做阶乘的精确计算时 (以9000!为例)，可比实用计算器快10倍。而当精确到30多位有效数字时，可比windows自带的计算器快上7500倍。其后的2001年1月，我在csdn上看到一个贴子，题目是“有谁可以用四行代码求出1000000的阶乘”，我回复了这个贴子，给出一个相对简洁的代码，这是我在网上公布的第一个大数阶乘的程序。这一时期，可以看作是我写阶乘计算器的第一个时期。

?

　　我写阶乘计算器的第二个时期始于2003年9月，在那时我写了一组专门计算阶乘的程序，按运行速度来分，分为三个级别的版本，初级版、中级版和高级版。初级版本的算法许多人都能想到，中级版则采用大数乘以大数的硬乘法，高级版本在计算大数乘法时引入分治法。期间在csdn社区发了两个贴子，“擂台赛：计算n!(阶乘)的精确值，速度最快者2000分送上”和“擂台赛：计算n!(阶乘)的精确值，速度最快者2000分送上（续）”。其高级算的版本完成于2003年11月。此后，郭先强于2004年5月10日也发表了系列贴子，“擂台：超大整数高精度快速算法”、“擂台：超大整数高精度快速算法(续)”和“擂台：超大整数高精度快速算法(续2)”,该贴重点展示了大数阶乘计算器的速度。这个贴子一经发表即引起了热列的讨论，除了我和郭先强先生外，郭雄辉也写了同样功能的程序，那时，大家都在持续改进自己的程序，看谁的程序更快。初期，郭先强的稍稍领先，中途郭子将apfloat的代码应用到阶乘计算器中，使得他的程序胜出，后期（2004年8月后）在我将程序作了进一步的改进后，其速度又稍胜于他们。在这个贴子中，arya提到一个开放源码的程序，它的大数乘法采用FNT＋CRT(快速数论变换＋中国剩余定理)。郭雄辉率先采用apflot来计算大数阶乘，后来郭先强和我也参于到apfloat的学习和改进过程中。在这点上，郭先强做得非常好，他在apfloat的基础上，成功地优化和改时算法，并应用到大数阶乘计算器上，同时他也将FNT算法应用到他的＜超大整数高精度快速算法库＞中，并在2004.10.18正式推出V3.0.2.1版。此后，我在2004年9月9日也完成一个采用FNT算法的版本，但却不及郭先强的阶乘计算器快。那时，郭先强的程序是我们所知的运算速度最快的阶乘计算器，其速度超过久负盛名的数学软件Mathematica和Maple,以及通用高精度算法库GMP。

　　我写阶乘计算器的第三个时间约开始于2006年，在2005年8月收到北大刘楚雄老师的一封e-mail，他提到了他写的一个程序在计算阶乘时比我们的更快。这使我非常吃惊，在询问后得知，其核心部分使用的是ooura写的FFT函数。ooura的FFT代码完全公开，是世界上运行的最快的FFT程序之一，从这点上，再次看到了我们和世界先进水平的差距。佩服之余，我决定深入学习FFT算法，看看能否写出和ooura速度相当或者更快的程序，同时一个更大计划开始形成，即写一组包括更多算法的阶乘计算器，包括使用FFT算法的终极版和使用无穷级数的stirling公式来计算部分精度的极速版，除此之外，我将重写和优化以前的版本，力争使速度更快，代码更优。这一计划的进展并不快，曾一度停止。

　　目前，csdn上blog数量正在迅速地增加，我也萌生了写blog的计划，借此机会，对大数阶乘之计算作一个整理，用文字和代码详述我的各个版本的算法和实现，同时也可能分析一些我在网上看到的别人写的程序，当然在这一过程中，我会继续编写未完成的版本或改写以前己经实现的版本，争取使我公开的第一份代码都是精品，这一过程可能是漫长的，但是我会尽力做下去。

?菜鸟篇

程序1，一个最直接的计算阶乘的程序

#include "stdio.h"
#include "stdlib.h" 
int main(int argc,char* argv[])
{
         long i,n,p;
         printf("n=?");
         scanf("%d",&n);
         p=1;
         for (i=1;i<=n;i++)
                  p*=i;
         printf("%d!=%d/n",p);
         return 0;
}

?

程序2，稍微复杂了一些，使用了递归，一个c++初学者写的程序

#include   <iostream.h>   
  long   int   fac(int   n);   
  void   main()   
  {   
          int   n;   
          cout<<"input   a   positive   integer:";   
          cin>>n;   
          long   fa=fac(n);   
          cout<<n<<"!   ="<<fa<<endl;   
  }   
  long   int   fac(int   n)   
  {   
          long   int   p;   
          if(n==0)   p=1;   
          else   
              p=n*fac(n-1);   
          return   p;   
  }   
  

程序点评，这两个程序在计算12以内的数是正确，但当n>12,程序的计算结果就完全错误了，单从算法上讲，程序并没有错，可是这个程序到底错在什么地方呢？看来程序作者并没有意识到，一个long型整数能够表示的范围是很有限的。当n>=13时，计算结果溢出，在C语言，整数相乘时发生溢出时不会产生任何异常，也不会给出任何警告。既然整数的范围有限，那么能否用范围更大的数据类型来做运算呢？这个主意是不错，那么到底选择那种数据类型呢？有人想到了double类型，将程序1中long型换成double类型，结果如下:

#include "stdio.h"
#include "stdlib.h"
 
int main(int argc,char* argv[])
{
   double i,p;
   printf("n=?");
   scanf("%lf",&n);
   p=1.0;
   for (i=1;i<=n;i++)
            p*=i;
   printf("%lf!=%.16g/n",p);
   return 0;
}

?

运行这个程序，将运算结果并和windows计算器对比后发现，当于在170以内时，结果在误差范围内是正确。但当N>=171,结果就不能正确显示了。这是为什么呢？和程序1类似，数据发生了溢出，即运算结果超出的数据类型能够表示的范围。看来C语言提供的数据类型不能满足计算大数阶乘的需要，为此只有两个办法。1.找一个能表示和处理大数的运算的类库。2.自己实现大数的存储和运算问题。方法1不在本文的讨论的范围内。本系列的后续文章将围绕方法2来展开。