阶乘算法优化「建议收藏」

大家好，又见面了，我是你们的朋友全栈君。

原文地址：http://blog.csdn.net/yxnk/article/details/1665052

我的感言：首先，有一个概念上的认知，即根据阶乘定义而来的常规算法，如果是long int型只能正确计算到12左右的阶乘，如果用double型只能正确计算170左右的阶乘，当然这些只是大概，需要结合实际平台进行验证。

下面是原文：

序

大数阶乘的计算是一个有趣的话题，从中学生到大学教授，许多人都投入到这个问题的探索和研究之中，并发表了他们自己的研究成果。如果你用阶乘作关键字在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”,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,n,p;

   printf(“n=?”);

   scanf(“%lf”,&n);

   p=1.0;

   for (i=1;i<=n;i++)

           p*=i;

   printf(“%lf!=%.16g/n”,n,p);

  return 0;

}

 

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

大数的表示

 

1.大数，这里提到的大数指有效数字非常多的数，它可能包含少则几十、几百位十进制数，多则几百万或者更多位十进制数。有效数字这么多的数只具有数学意义，在现实生活中，并不需要这么高的精度，比如银河系的直径有10万光年，如果用原子核的直径来度量，31位十进制数就可使得误差不超过一个原子核。

 

2.大数的表示：

 2.1定点数和浮点数

　我们知道，在计算机中，数是存贮在内存(RAM)中的。在内存中存储一个数有两类格式，定点数和浮点数。定点数可以精确地表示一个整数，但数的范围相对较小，如一个32比特的无符号整数可表示0－4294967295之间的数，可精确到9－10位数字(这里的数字指10进制数字，如无特别指出，数字一律指10进制数字),而一个8字节的无符号整数则能精确到19位数字。浮点数能表示更大的范围，但精度较低。当表示的整数很大的，则可能存在误差。一个8字节的双精度浮点数可表示2.22*10^-308到 1.79*10^308之间的数,可精确到15－16位数字.

2.2日常生活中的数的表示：

　对于这里提到的大数，上文提到的两种表示法都不能满足需求。为此，必需设计一种表示法来存储大数。我们以日常生活中的十进制数为例，看看是如何表示的。如一个数N被写成“12345”,则这个数可以用一个数组a来表示，a[0]=1,a[1]=2,a[2]=3,a[3]=4,a[4]=5,这时数N=a[4]*10^0+a[3]*10^1+a[2]*10^2+a[1]*10^3+a[0]*10^4,(10^4表示10的4次方，下同),10^i可以叫做权，在日常生活中，a[0]被称作万位，也说是说它的权是10000，类似的，a[1]被称作千位，它的权是1000。

 

   2.3　大数在计算机语言表示：

　　在日常生活中，我们使用的阿拉伯数字只有0－9共10个，按照书写习惯，一个字符表示1位数字。计算机中，我们常用的最小数据存储单位是字节，C语言称之为char,多个字节可表示一个更大的存储单位。习惯上，两个相邻字节组合起来称作一个短整数，在32位的C语言编译器中称之为short,汇编语语言一般记作word,4个相邻的字节组合起来称为一个长整数，在32位的C语言编译器中称之为long,汇编语言一般记作DWORD。在计算机中，按照权的不同，数的表示可分为两种，2进制和10进制，严格说来，应该是2^k进制和10^K进制，前者具占用空间少，运算速度快的优点。后者则具有容易显示的优点。我们试举例说明：

   例1：若一个大数用一个长为len的short型数组A来表示，并采用权从大到小的顺序依次存放，数N表示为A[0] * 65536^(len-1)+A[1] * 65536^(len-2)+…A[len-1] * 65536^0,这时65536称为基，其进制2的16次方。

   例2：若一个大数用一个长为len的short型数组A来表示并采用权从大到小的顺序依次存放，数N=A[0] * 10000^(len-1)+A[1] * 10000^(len-2)+…A[len-1] * 10000^0,这里10000称为基，其进制为10000，即：10^4，数组的每个元素可表示4位数字。一般地，这时数组的每一个元素为小于10000的数。类似的，可以用long型数组，基为2＾32＝4294967296来表示一个大数;当然可以用long型组，基为1000000000来表示，这种表示法，数组的每个元素可表示9位数字。当然，也可以用char型数组，基为10。最后一种表示法，在新手写的计算大数阶乘程序最为常见，但计算速度却是最慢的。使用更大的基，可以充分发挥CPU的计算能力，计算量将更少，计算速度更快，占用的存储空间也更少。

 2.4大尾序和小尾序，我们在书写一个数时，总是先写权较大的数字，后写权较小的数字，但计算机中的数并不总是按这个的顺序存放。小尾（Little Endian）就是低位字节排放在内存的低端，高位字节排放在内存的高端。例如对于一个4字节的整数0x12345678,将在内存中按照如下顺序排放, Intel处理器大多数使用小尾(Little Endian)字节序。

    Address[0]: 0x78

    Address[1]: 0x56

Address[2]: 0x34

    Address[3]:0x12

大尾（Big Endian）就是高位字节排放在内存的低端，低位字节排放在内存的高端。例如对于一个4字节的整数0x12345678,将在内存中按照如下顺序排放, Motorola处理器大多数使用大尾(Big Endian)字节序。

Address[0]: 0x12

    Address[1]: 0x34

Address[2]: 0x56

    Address[3]:0x78

 　类似的，一个大数的各个元素的排列方式既可以采用低位在前的方式，也可以采用高位在前的方式，说不上那个更好，各有利弊吧。我习惯使用高位在前的方式。　　　

2.5不完全精度的大数表示：

　尽管以上的表示法可准确的表示一个整数，但有时可能只要求计算结果只精确到有限的几位。如用 windows自带的计算器计算1000的阶乘时，只能得到大约32位的数字，换名话说，windows计算器的精度为32位。1000的阶乘是一个整数，但我们只要它的前几位有效数字，象windows计算器这样，只能表示部分有效数字的表示法叫不完全精度，不完全精度不但占用空间省，更重要的是，在只要求计算结果为有限精度的情况下，可大大减少计算量。大数的不完全精度的表示法除了需要用数组存储有数数字外，还需要一个数来表示第一个有效数字的权，10的阶乘约等于4.023872600770937e+2567，则第一个有效数字的权是10^2567，这时我们把2567叫做阶码。在这个例子中，我们可以用一个长为16的char型数组和一个数来表示，前者表示各位有效数字，数组的各个元素依次为:4,0,2,3,8,7,2,6,0,0,7,7,0,9,3,7，后者表示阶码，值为2567。

 

  

2.6大数的链式存储法

 如果我们搜索大数阶乘的源代码，就会发现，有许多程序采用链表存储大数。尽管这种存储方式能够表示大数，也不需要事先知道一个特定的数有多少位有效数字，可以在运算过程中自动扩展链表长度。但是，如果基于运算速度和内存的考虑，强烈不建议采用这种存储方式，因为：

1.     这种存储方式的内存利用率很低。基于大数乘法的计算和显示，一般需要定义双链表，假如我们用1个char表示1位十进制数，则可以这样定义链表的节点：

          struct _node

          {

struct _node* pre;

struct _node* next;

char n; 

};

当编译器采用默认设置，在通常的32位编译器，这个结构体将占用12字节。但这并不等于说，分配具有1000个节点的链表需要1000*12字节。不要忘记，操作系统或者库函数在从内存池中分配和释放内存时，也需要维护一个链表。实验表明，在VC编译的程序，一个节点总的内存占用量为 sizeof(struct _node) 向上取16的倍数再加8字节。也就是说，采用这种方式表示n位十进制数需要 n*24字节，而采用1个char型数组仅需要n字节。

2采用链表方式表示大数的运行速度很慢.

2.1如果一个大数需要n个节点，需要调用n次malloc(C)或new(C++)函数，采用动态数组则不要用调用这么多次malloc.

2.2 存取数组表示的大数比链表表示的大数具有更高的cache命中率。数组的各个元素的地址是连续的，而链表的各个节点在内存中的地址是不连续的，而且具有更大的数据量。因此前者的cache的命中率高于后者，从而导致运行速度高于后者。

2.3对数组的顺序访问也比链表快，如p1表示数组当前元素的地址，则计算数组的下一个地址时一般用p1++,而对链表来说则可能是p2=p2->next,毫无疑问，前者的执行速度更快。

 

近似计算之一

 

在＜阶乘之计算从入门到精通－菜鸟篇＞中提到，使用double型数来计算阶乘，当n>170,计算结果就超过double数的最大范围而发生了溢出，故当n＞170时，就不能用这个方法来计算阶乘了，果真如此吗？No,只要肯动脑筋,办法总是有的。

通过windows计算器，我们知道，171！＝1.2410180702176678234248405241031e+309，虽然这个数不能直接用double型的数来表示，但我们可以用别的方法来表示。通过观察这个数，我们发现，这个数的表示法为科学计算法，它用两部分组成，一是尾数部分1.2410180702176678234248405241031，另一个指数部分309。不妨我们用两个数来表示这个超大的数，用double型的数来表示尾数部分，用一个long型的数来表示指数部分。这会涉及两个问题：其一是输出，这好说，在输出时将这两个部分合起来就可以了。另一个就是计算部分了，这是难点所在（其实也不难）。下面我们分析一下，用什么方法可以保证不会溢出呢？

我们考虑170！，这个数约等于7.257415e+306，可以用double型来表示，但当这个数乘以171就溢出了。我们看看这个等式：

7.257415e+306

＝7.257415e+306 * 10^0 (注1)（如用两个数来表示，则尾数部分7.257415e+306，指数部分0)

＝(7.257415e+306 / 10^300 )* (10^0*10^300)

=（7.257415e6）*（10 ^ 300）　（如用两个数来表示，则尾数部分7.257415e+6，指数部分300）

 

依照类似的方法，在计算过程中，当尾数很大时，我们可以重新调整尾数和指数，缩小尾数，同时相应地增大指数，使其表示的数的大小不变。这样由于尾数很小，再乘以一个数就不会溢出了，下面给出完整的代码。

 

程序3.

#include “stdafx.h”

#include “math.h”

#define MAX_N 10000000.00          //能够计算的最大的n值，如果你想计算更大的数对数，可将其改为更大的值

#define MAX_MANTISSA   (1e308/MAX_N)    //最大尾数 

struct bigNum

{

    double n1;     //表示尾数部分

     int n2;   //表示指数部分

  };

 

void calcFac(struct bigNum *p,int n)

{

     int i;

     doubleMAX_POW10_LOG=(floor(log10(1e308/MAX_N))); //最大尾数的常用对数的整数部分,

     double MAX_POW10=    (pow(10.00, MAX_POW10_LOG)); // 10 ^ MAX_POW10_LOG

        p->n1=1;

     p->n2=0;

     for (i=1;i<=n;i++)

     {

          if (p->n1>=MAX_MANTISSA)

          {

               p->n1 /= MAX_POW10;

               p->n2 += MAX_POW10_LOG;

          }

          p->n1 *=(double)i;

     }

}

 

void printfResult(struct bigNum *p,char buff[])

{

     while (p->n1 >=10.00 )

     {p->n1/=10.00; p->n2++;}

     sprintf(buff,”%.14fe%d”,p->n1,p->n2);

}

 

int main(int argc, char* argv[])

{

     struct bigNum r;

     char buff[32];

     int n;

    

     printf(“n=?”);

     scanf(“%d”,&n);

     calcFac(&r,n);           //计算n的阶乘

     printfResult(&r,buff);   //将结果转化一个字符串

        printf(“%d!=%s/n”,n,buff);

     return 0;

}

 

以上代码中的数的表示方式为：数的值等于尾数乘以 10 ^指数部分，当然我们也可以表示为：尾数乘以 2 ^指数部分，这们将会带来这样的好处，在调整尾数部分和指数部分时，不用除法，可以依据浮点数的格式直读取阶码和修改阶码(上文提到的指数部分的标准称呼)，同时也可在一定程序上减少误差。为了更好的理解下面的代码，有必要了解一下浮点数的格式。浮点数主要分为32bit单精度和64bit双精度两种。本方只讨论64bit双精度(double型)浮点数的格式，一个double型浮点数包括8个字节(64bit)，我们把最低位记作bit0,最高位记作bit63,则一个浮点数各个部分定义为:第一部分尾数：bit0至bit51，共计52bit，第二部分阶码:bit52-bit62,共计11bit，第三部分符号位:bit63，0:表示正数，1表示负数。如一个数为0.xxxx * 2^ exp,则exp表示指数部分，范围为－1023到1024，实际存储时采用移码的表示法，即将exp的值加上0x3ff，使其变为一个0到2047范围内的一个值。函数GetExpBase2中各语句含义如下：1.“(*pWord & 0x7fff)”，得到一个bit48-bit63这个16bit数，最高位清0。2.“>>4”,将其右移4位以清除最低位的4bit尾数，变成一个11bit的数（最高位5位为零）。3(rank-0x3ff)”,减去0x3ff还原成真实的指数部分。以下为完整的代码。

 

程序4：

#include “stdafx.h”

#include “math.h”

#define MAX_N 10000000.00      //能够计算的最大的n值，如果你想计算更大的数对数，可将其改为更大的值

#define MAX_MANTISSA   (1e308/MAX_N) //最大尾数

typedef unsigned short WORD;

 

struct bigNum

{

double n1;     //表示尾数部分

int n2;   //表示阶码部分

};

short GetExpBase2(double a) //获得 a的阶码
  {

// 按照IEEE 754浮点数格式，取得阶码，仅仅适用于Intel系列 cpu

        WORD *pWord=(WORD *)(&a)+3;

    WORD rank = ( (*pWord & 0x7fff) >>4 );

    return (short)(rank-0x3ff);

}

 double GetMantissa(double a) //获得 a的尾数

{

// 按照IEEE 754浮点数格式，取得尾数，仅仅适用于Intel系列 cpu

       WORD *pWord=(WORD *)(&a)+3;

*pWord &= 0x800f; //清除阶码

*pWord |= 0x3ff0; //重置阶码

return a;

}

 

void calcFac(struct bigNum *p,int n)

{

int i;

p->n1=1;

p->n2=0;

for (i=1;i<=n;i++)

{

if (p->n1>=MAX_MANTISSA)//继续相乘可能溢出，调整之

      {

           p->n2 += GetExpBase2(p->n1);

           p->n1 = GetMantissa(p->n1);

      }

      p->n1 *=(double)i;

}

}

 

void printfResult(struct bigNum *p,char buff[])

{

double logx=log10(p->n1)+ p->n2 * log10(2);//求计算结果的常用对数

int logxN=(int)(floor(logx)); //logx的整数部分

sprintf(buff,”%.14fe%d”,pow(10,logx-logxN),logxN);//转化为科学计算法形式的字符串

}

 

int main(int argc, char* argv[])

{

struct bigNum r;

char buff[32];

int n;

printf(“n=?”);

scanf(“%d”,&n);

calcFac(&r,n);           //计算n的阶乘

printfResult(&r,buff);   //将结果转化一个字符串

printf(“%d!=%s/n”,n,buff);

return 0;

}

 

程序优化的威力：

程序4是一个很好的程序，它可以计算到1千万（当n更大时，p->n2可能溢出）的阶乘，但是从运行速度上讲，它仍有潜力可挖，在采用了两种优化技术后，（见程序5），速度竟提高5倍，甚至超出笔者的预计。

第一种优化技术，将频繁调用的函数定义成inline函数，inline是C++关键字，如果使用纯C的编译器，可采用MACRO来代替。

第二种优化技术，将循环体内的代码展开，由一个循环步只做一次乘法，改为一个循环步做32次乘法。

实际速度：计算10000000！，程序4需要0.11667秒，程序5只需要0.02145秒。测试环境为迅驰1.7G,256M RAM。关于程序优化方面的内容，将在后续文章专门讲述。下面是被优化后的部分代码，其余代码不变。

 

程序5的部分代码：

 inline short GetExpBase2(double a) //获得 a的阶码

{

// 按照IEEE 754浮点数格式，取得阶码，仅仅适用于Intel系列 cpu

    WORD *pWord=(WORD *)(&a)+3;

    WORD rank = ( (*pWord & 0x7fff) >>4 );

    return (short)(rank-0x3ff);

}

inline double GetMantissa(double a) //获得 a的尾数 

{

// 按照IEEE 754浮点数格式，取得尾数，仅仅适用于Intel系列 cpu

    WORD *pWord=(WORD *)(&a)+3;

   *pWord &= 0x800f; //清除阶码

    *pWord |= 0x3ff0; //重置阶码

 

    return a;

 

}

 

void calcFac(struct bigNum *p,int n)

{

   int i,t;

   double f,max_mantissa;

   p->n1=1;p->n2=0;t=n-32;

   for (i=1;i<=t;i+=32)

   {

        p->n2 += GetExpBase2(p->n1); p->n1 = GetMantissa(p->n1);

        f=(double)i;

        p->n1 *=(double)(f+0.0);      p->n1 *=(double)(f+1.0);

        p->n1 *=(double)(f+2.0);      p->n1 *=(double)(f+3.0);

        p->n1 *=(double)(f+4.0);      p->n1 *=(double)(f+5.0);

        p->n1 *=(double)(f+6.0);      p->n1 *=(double)(f+7.0);

        p->n1 *=(double)(f+8.0);      p->n1 *=(double)(f+9.0);

        p->n1 *=(double)(f+10.0);          p->n1 *=(double)(f+11.0);

        p->n1 *=(double)(f+12.0);          p->n1 *=(double)(f+13.0);

        p->n1 *=(double)(f+14.0);          p->n1 *=(double)(f+15.0);

        p->n1 *=(double)(f+16.0);          p->n1 *=(double)(f+17.0);

        p->n1 *=(double)(f+18.0);          p->n1 *=(double)(f+19.0);

        p->n1 *=(double)(f+20.0);          p->n1 *=(double)(f+21.0);

        p->n1 *=(double)(f+22.0);          p->n1 *=(double)(f+23.0);

        p->n1 *=(double)(f+24.0);          p->n1 *=(double)(f+25.0);

        p->n1 *=(double)(f+26.0);          p->n1 *=(double)(f+27.0);

        p->n1 *=(double)(f+28.0);          p->n1 *=(double)(f+29.0);

        p->n1 *=(double)(f+30.0);          p->n1 *=(double)(f+31.0);

   }

  

   for (;i<=n;i++)

   {

        p->n2 += GetExpBase2(p->n1);

        p->n1 = GetMantissa(p->n1);

        p->n1 *=(double)(i);

   }

}

 

注1：10＾0，表示10的0次方

近似计算之二

 

在《阶乘之计算从入门到精通－近似计算之一》中，我们采用两个数来表示中间结果，使得计算的范围扩大到1千万，并可0.02秒内完成10000000！的计算。在保证接近16位有效数字的前提下，有没有更快的算法呢。很幸运，有一个叫做Stirling的公式，它可以快速计算出一个较大的数的阶乘，而且数越大，精度越高。有http://mathworld.wolfram.com查找Stirling’s Series可找到2个利用斯特林公式求阶乘的公式，一个是普通形式，一个是对数形式。前一个公式包含一个无穷级数和的形式，包含级数前5项的公式为n!=sqrt(2*PI*n)*(n/e)ⁿ*(1+ 1/12/n+ 1/288/n² –139/51840/n³-571/2488320/n⁴+…),这里的PI为圆周率，e为自然对数的底。后一个公式也为一个无穷级数和的形式，一般称这个级数为斯特林(Stirling)级数,包括级数前3项的n!的对数公式为：ln(n!)=0.5*ln(2*PI)+(n+0.5)*ln(n)-n+(1/12/n -1/360/n³ + 1/1260/n⁵)-…,下面我们分别用这两个公式计算n!.

完整的代码如下：

#include “stdafx.h”

#include “math.h”

#define PI       3.1415926535897932384626433832795

#define E 2.7182818284590452353602874713527

struct bigNum

{

       double n;//科学计数法表示的尾数部分

       int    e;//科学计数法表示的指数部分,若一个bigNum为x,这x=n * 10^e

};

const double a1[]=

{     1.00, 1.0/12.0, 1.0/288, -139/51840,-571.0/2488320.0 };

const double a2[]=

{     1.0/12.0, -1.0/360, 1.0/1260.0 };

void printfResult(struct bigNum *p,char buff[])

{

       while (p->n >=10.00 )

       {p->n/=10.00; p->e++;}

       sprintf(buff,”%.14fe%d”,p->n,p->e);

}

// n!=sqrt(2*PI*n)*(n/e)^n*(1+ 1/12/n+ 1/288/n^2 -139/51840/n^3-571/2488320/n^4+…)

void calcFac1(struct bigNum *p,int n)

{

       double logx,

              s,           //级数的和

              item;  //级数的每一项

       int i;

       // x^n= pow(10,n * log10(x));

       logx= n* log10((double)n/E);

       p->e= (int)(logx);   p->n= pow(10.0, logx-p->e);

       p->n *= sqrt( 2* PI* (double)n);

      

      //求(1+ 1/12/n+ 1/288/n^2 -139/51840/n^3-571/2488320/n^4+…)

       for (item=1.0,s=0.0,i=0;i<sizeof(a1)/sizeof(double);i++)

       {

              s+= item * a1[i];

              item /= (double)n; //item= 1/(n^i)

       }

       p->n *=s;

}

//ln(n!)=0.5*ln(2*PI)+(n+0.5)*ln(n)-n+(1/12/n -1/360/n^3 + 1/1260/n^5 -…)

void calcFac2(struct bigNum *p,int n)

{

       double logR;

       double s,//级数的和

       item;      //级数的每一项

       int i;

      

       logR=0.5*log(2.0*PI)+((double)n+0.5)*log(n)-(double)n;

      

       //s= (1/12/n -1/360/n^3 + 1/1260/n^5)

       for (item=1/(double)n,s=0.0,i=0;i<sizeof(a2)/sizeof(double);i++)

       {

              s+= item * a2[i];

              item /= (double)(n)* (double)n; //item= 1/(n^(2i+1))

       }

       logR+=s;

      

       //根据换底公式，log10(n)=ln(n)/ln(10)

       p->e = (int)( logR / log(10));

       p->n = pow(10.00, logR/log(10) – p->e);

}

int main(int argc, char* argv[])

{

       struct bigNum r;

       char buff[32];

       int n;

       printf(“n=?”);

       scanf(“%d”,&n);

      

       calcFac1(&r,n);           //用第一种方法，计算n的阶乘

       printfResult(&r,buff);   //将结果转化一个字符串

       printf(“%d!=%s by method 1/n”,n,buff);

       calcFac2(&r,n);           //用第二种方法，计算n的阶乘

       printfResult(&r,buff);   //将结果转化一个字符串

       printf(“%d!=%s by method 2/n”,n,buff);

       return 0;

}

程序运行时间的测量

 

算法的好坏有好多评价指标，其中一个重要的指标是时间复杂度。如果两个程序完成一个同样的任务，即功能相同，处理的数据相同，那么运行时间较短者为优。操作系统和库函数一般都提供了对时间测量的函数，这么函数一般都会返回一个代表当前时间的数值，通过在运行某个程序或某段代码之前调用一次时间函数来得到一个数值，在程序或者代码段运行之后再调用一次时间函数来得到另一个数值，将后者减去前者即为程序的运行时间。

　在windwos平台(指windwow95及以后的版本，下同),常用的用于测量时间的函数或方法有三种：1.API函数GetTickCount或C函数clock,2.API函数QueryPerformanceCounter，　3:汇编指令RDSTC

1．API函数GetTickCount：

函数原形：DWORD GetTickCount(VOID)；

该函数取回从电脑开机至现在的毫秒数，即每个时间单位为1毫秒。他的分辨率比较低，常用在测量用时较长程序，如果你的程序用时为100毫秒以上，可以使用这个函数.另一个和GetTickCount类似的函数是clock，该函数的回的时间的单位的是CLOCKS_PER_SEC，在windows95/2000操作系统，该值是1000,也就是说，在windows平台，这两个函数的功能几乎完全相同。

2.API函数QueryPerformanceCounter：

函数原形：BOOL QueryPerformanceCounter( LARGE_INTEGER *lpPerformanceCount);该函数取回当前的高分辨值performance计数器，用一个64bit数来表示。如果你的硬件不支持高分辨performance计数器，系统可能返加零。不像GetTickCount，每个计数器单位表示一个固定的时间1毫秒，为了知道程序确切的执行时间，你需要调用函数QueryPerformanceFrequency来得到每秒performance计数器的次数，即频率。

3.汇编指令RDTSC:

RDTSC 指令读取CPU内部的“时间戳(TimeStamp)”，它是一个64位无符号数计数器，这条指令执行完毕后，存储在EDX:EAX寄存中。该指令从intel奔腾CPU开始引入，一些老式的CPU不支持该指令，奔腾后期的CPU包括AMD的CPU均支持这条指令。和QueryPerformanceCounter类似，要想知道程序的确实的执行时间，必须知道CPU的频率，即平常所说的CPU的主频。不幸的是没有现成的函数可以得到CPU的频率。一种办法可行的办法延时一段指定时间，时间的测量可以用QueryPerformanceCounter来做，在这段时间的开始和结束调用RDTSC,得到其时钟数的差值，然后除以这段时间的的秒数就可以了。

 

下面的代码给出使用3个函数封装和测试代码，用RDTSC指令来计时的代码参考了一个Ticktest的源代码，作者不详。

getTime1，使用GetTickCount返回一个表示当前时间的值，单位秒。

getTime2，和getTime1类似，精度更高。

getTime3，返回一个64bit的一个计数器，欲转换为秒，需除以CPU频率。示例代码见函数test3.

#include “stdafx.h”

#include “windows.h”

#include “tchar.h”

double getTime1()

{

       DWORD t=GetTickCount();

       return (double)t/1000.00;

}

double getTime2()//使用高精度计时器

{     

       static LARGE_INTEGER s_freq;

       LARGE_INTEGER performanceCount;

       double t;

       if (s_freq.QuadPart==0)

       {

              if ( !QueryPerformanceFrequency( &s_freq))

                     return 0;

       }

      

       QueryPerformanceCounter( &performanceCount );

       t=(double)performanceCount.QuadPart / (double)s_freq.QuadPart;

       return t;

}

void test1()

{

       double t1,t2;

       t1=getTime1();

       Sleep(1000);

       t2=getTime1()-t1;

       printf(“It take %.8f second/n”,t2);

}

void test2()

{

       double t1,t2;

       t1=getTime2();

       Sleep(1000);

       t2=getTime2()-t1;

       printf(“It take %.8f second/n”,t2);

}

inline BOOL isNTOS() //检测是否运行在NT操作系统

{

       typedef BOOL (WINAPI *lpfnGetVersionEx) (LPOSVERSIONINFO);

       static int bIsNT=-1;

       if (bIsNT!=1)

              return (BOOL)bIsNT;

      // Get Kernel handle

       HMODULE hKernel32 = GetModuleHandle(_T(“KERNEL32.DLL”));

       if (hKernel32 == NULL)

              return FALSE;

 #ifdef _UNICODE

    lpfnGetVersionEx lpGetVersionEx = (lpfnGetVersionEx) GetProcAddress(hKernel32, _T(“GetVersionExW”));

 #else

    lpfnGetVersionEx lpGetVersionEx = (lpfnGetVersionEx) GetProcAddress(hKernel32, _T(“GetVersionExA”));

 #endif

 

       if (lpGetVersionEx)

       {

              OSVERSIONINFO osvi;

              memset(&osvi, 0, sizeof(OSVERSIONINFO));

              osvi.dwOSVersionInfoSize = sizeof(OSVERSIONINFO);

              if (!lpGetVersionEx(&osvi))

                     bIsNT=FALSE;

              else

                     bIsNT=(osvi.dwPlatformId == VER_PLATFORM_WIN32_NT);

       }

       else

       {

             //Since GetVersionEx is not available we known that

              //we are running on NT 3.1 as all modern versions of NT and

              //any version of Windows 95/98 support GetVersionEx

              bIsNT=TRUE;

       }

       return bIsNT;

}

inline static BOOL checkRDSTC()//检测CPU是否支持RDSTC指令

{

       static int bHasRDSTC= -1;

       SYSTEM_INFO sys_info;

      

       if ( bHasRDSTC !=-1 )

              return (BOOL)bHasRDSTC;

       GetSystemInfo(&sys_info);

       if (sys_info.dwProcessorType==PROCESSOR_INTEL_PENTIUM)

       {

              try

              {

                     _asm

                     {

                     _emit 0x0f                           ; rdtsc    

                     _emit 0x31

                     }

              }

              catch (…)      // Check to see if the opcode is defined.

              {

                     bHasRDSTC=FALSE; return FALSE;

              }

             // Check to see if the instruction ticks accesses something that changes.

              volatile ULARGE_INTEGER ts1,ts2;

              _asm

              {

                     xor eax,eax

                     _emit 0x0f                                  ; cpuid

                    _emit 0xa2

                     _emit 0x0f                                  ; rdtsc

                     _emit 0x31

                    mov ts1.HighPart,edx

                     mov ts1.LowPart,eax

                     xor eax,eax

                     _emit 0x0f                                  ; cpuid

                    _emit 0xa2

                     _emit 0x0f                                  ; rdtsc

                     _emit 0x31

                    mov ts2.HighPart,edx

                     mov ts2.LowPart,eax

              }

             // If we return true then there’s a very good chance it’s a real RDTSC instruction!

              if (ts2.HighPart>ts1.HighPart)

                  bHasRDSTC=TRUE;

              else if (ts2.HighPart==ts1.HighPart && ts2.LowPart>ts1.LowPart)

                     bHasRDSTC=TRUE;

              else

              {

                     printf(“RDTSC instruction NOT present./n”);

                     bHasRDSTC=FALSE;

              }

       }

       else

              bHasRDSTC=FALSE;

       return bHasRDSTC;

}

//***********************************************

void getTime3( LARGE_INTEGER *pTime) //返加当前CPU的内部计数器

{

       if (checkRDSTC())

       {

              volatile ULARGE_INTEGER ts;

      //on NT don’t bother disabling interrupts as doing

       //so will generate a priviledge instruction exception

              if (!isNTOS())

                     _asm cli

          //—————-     

        _asm

              {

                     xor eax,eax

           //————-save rigister

                     push ebx

                     push ecx

                    

                     _emit 0x0f                                  ; cpuid – serialise the processor

                    _emit 0xa2

                    

                    //————

                     _emit 0x0f                                  ; rdtsc

                     _emit 0x31

                    

                     mov ts.HighPart,edx

                     mov ts.LowPart,eax

                    

                    pop ecx

                     pop ebx

              }

       //—————–

              if (!isNTOS())

                     _asm      sti

             //———      

        pTime->QuadPart=ts.QuadPart;

       }

       else

           pTime->QuadPart=0;

}

// maxDetermainTime:最大测定时间,单位毫秒，在首次调用该函数时，

// 将花费maxDetermineTime的时间来测定CPU频率，以后的调用将直接返加静态变量的值

double GetCPUFrequency(DWORD maxDetermineTime )

{

       static double CPU_freq;

       LARGE_INTEGER period,t1,t2;

       register LARGE_INTEGER goal,current;

      

       if (CPU_freq>1000)     //this value have been initilization

              return CPU_freq;

       if (!QueryPerformanceFrequency(&period) || !checkRDSTC())

       {

              CPU_freq=-1.00;

              return CPU_freq;

       }

       QueryPerformanceCounter(&goal);

       goal.QuadPart += period.QuadPart * maxDetermineTime/1000;

       getTime3( &t1);  //开始计时

       do    //延时maxDetermineTime毫秒

       {

              QueryPerformanceCounter(&current);

       } while(current.QuadPart<goal.QuadPart);

       getTime3(&t2);     //结束计时

      

       CPU_freq=double((t2.QuadPart-t1.QuadPart)*1000/maxDetermineTime);

      

       char buff[100];

       sprintf(buff,”Estimated the processor clock frequency =%gHz/n”,CPU_freq);

    ::MessageBox(NULL,buff,””,MB_OK);

       return CPU_freq;

}

void test3()

{

       LARGE_INTEGER t,t1,t2;

       double f1,f2;

      

       GetCPUFrequency(100);//花费0.1秒时间计算CPU频率

       f1=getTime2();

       getTime3(&t1);

       Sleep(1000);

       getTime3(&t2);

       f2=getTime2();

       t.QuadPart=t2.QuadPart-t1.QuadPart;

       printf(“It take %.8f second by getTime3/n”,(double)t.QuadPart/GetCPUFrequency(100));

       printf(“It take %.8f second by getTime2/n”,f2-f1);

}

int main(int argc, char* argv[])

{

       test1();

       test2();

       test3();

       return 0;

}

入门篇之一

 

在《大数阶乘之计算从入门到精通－大数的表示》中，我们学习了如何表示和存储一个大数。在这篇文章中，我们将讨论如何对大数做乘法运算，并给出一个可以求出一个大整数阶乘的所有有效数字的程序。

大整数的存储和表示已经在上一篇文章做了详细的介绍。其中最简单的表示法是:大数用一个字符型数组来表示，数组的每一个元素表示一位十进制数字，高位在前，低位在后。那么，用这种表示法，如何做乘法运算呢？其实这个问题并不困难，可以使用模拟手算的方法来实现。回忆一下我们在小学时，是如何做一位数乘以多位数的乘法运算的。例如：2234*8。

  

 

我们将被乘数表示为一个数组A[], a[1],a[2],a[3],a[4]分别为2,2,3,4,a[0]置为0。

 

Step1: 从被乘数的个位a[4]起，取出一个数字4.

Step2: 与乘数8相乘，其积是两位数32，其个位数2作为结果的个位,存入a[4],十位数3存入进位c。

Step3: 取被乘数的上一位数字a[3]与乘数相乘，并加上上一步计算过程的进位C,得到27，将这个数的个位7作为结果的倒数第二位，存入a[3]，十位数2存入进位c。

Step4：重复Step3,取a[i]（i依次为4,3,2,1）与乘数相乘并加上c,其个位仍存入a[i],　十位数字存入c，直到i等于1为止。

Step5:将最后一步的进位c作为积的最高位a[0]。

 

这一过程其实和小学学过的多位数乘以一位数的珠算乘法一模一样，学过珠算乘法的朋友还有印象吗？

 

在计算大数阶乘的过程中，乘数一般不是一位数字，那么如何计算呢？我们可以稍作变通，将上次的进位加上本次的积得到数P,　将P除以10的余数做为结果的本位，将P除以10的商作为进位。当被乘数的所有数字都和乘数相乘完毕后，将进位C放在积的最前面即可。下面给出C语言代码。

一个m位数乘以n位数，其结果为m+n-1,或者m+n位，所以需首先定义一个至少m+n个元素的数组，并置前n位为0。

 

计算一个m位的被乘数乘以一个n位的整数k，积仍存储于数组a

 

 

void mul(unsigned char a[],unsigned long k,int m,int n)

{

     int i;

    unsigned long p;

    unsigned long c=0;

 

    for ( i=m+n-1; i>=n;i–)

    {

           p= a[i] * k +c;

           a[i]=(unsigned char)( p % 10);

           c= p / 10;

    }

  

    while (c>0)

    {

           a[i]=(unsigned char)( c % 10);

           i–;

           c /=10;

    }

}

 

int main(int argc, char* argv[])

{

    int i;

    unsigned char a[]={0,0,0,2,3,4,5};

    mul(a,678,4,3);

    i=0;

    while ( a[i]==0)

           i++;

    for (;i<4+3;i++)

        printf(“%c”,a[i]+’0’); //由于数a[i]（0<=a[i] <=9）对应的可打印字任符为’0’到’9’,所以显示为i＋’0’

               return 0;

}

 

从上面的例子可知，在做乘法之前，必须为数组保留足够的空间。具体到计算n!的阶乘时，必须准备一个能容纳的n!的所有位数的数组或者内存块。即数组采有静态分配或者动态分配。前者代码简洁，但只适应于n小于一个固定的值，后者灵活性强，只要有足够的内存，可计算任意n的阶乘，我们这里讨论后一种情况，如何分配一块大小合适的内存。

n!有多少位数呢？我们给出一个近似的上限值：n! <(n+1)/2的n次方，下面是推导过程。

Caes 1: n是奇数，则中间的那个数mid= (n+1)/2, 除了这个数外，我们可以将1到n之间的数分成n/2组，每组的两个数为 mid-i和mid+i (i=1到mid-1),如1,2,3,4,5,6,7可以分为数4，和3对数，它们是(3,5),(2,6)和(1,7),容易知道，每对数的积都于小mid*mid，故n!小于(n+1)/2的n的次方。

 

Case 2: n是个偶数，则中间的两个数(n－1)/2和(n+1)/2,我们将(n+1)/2记做mid,则其它的几对数是(mid-2,mid+1),(mid-3)(mid+2)等等，容易看出,n!小于mid的n次方。

由以上两种情况可知，对于任意大于1的正整数n, n!<(n+1)/2的n次方。

如果想求出n!更准确的上限，可以使用司特林公式，参见该系列文章《阶乘之计算从入门到精通－近似计算之二》。

 

到此，我们已经解决大数阶乘之计算的主要难题，到了该写出一个完整程序的时候了，下面给出一个完整的代码。

 

#include “stdio.h”

#include “stdlib.h”

#include “memory.h”

#include “math.h”

#include “malloc.h”

void calcFac(unsigned long n)

{

   unsigned long i,j,head,tail;

int blkLen=(int)(n*log10((n+1)/2)); //计算n!有数数字的个数

   blkLen+=4;  //保险起见，多加4位

’

  if (n<=1)

  {       printf(“%d!=0/n”,n);     return;}

 

  char *arr=(char *)malloc(blkLen);       

   if (arr==NULL)

   {       printf(“alloc memory fail/n”); return ;}

 

   memset(arr,0,sizeof(char)*blkLen);

   head=tail=blkLen-1;

   arr[tail]=1;

  

   for (i=2;i<=n;i++)

   {

           unsigned long c=0;

           for (j=tail;j>=head;j–)

           {

                    unsigned long prod=arr[j] * i +c;

                    arr[j]=(char)( prod % 10);

                    c= prod / 10;

           }

           while (c>0)

           {

                    head–;   

                    arr[head]=(char)(c % 10);

                    c/=10;

           }

   }

   printf(“%d!=”,n);

   for (i=head;i<=tail;i++)

           printf(“%c”,arr[i]+’0′);

   printf(“/n”);

 

   free(arr);

}

 

void testCalcFac()

{

    int n;

    while (1)

    {

            printf(“n=?”);

            scanf(“%ld”,&n);

            if (n==0)       

                   break;

            calcFac(n);

    }

}

 

int main(int argc, char* argv[])

{

    testCalcFac();

    return 0;

}

用Stirling逼近近似计算阶乘的探讨与应用

江苏省赣榆高级中学仲晨

myheimu@yahoo.com.cn

【关键词】：Stirling逼近，阶乘，极限论，微积分，数学实验，计算机算法

 

“阶乘”（factorial）在信息学竞赛中具有重要角色，更广泛的说，“阶乘”在数学领域也是占有重要地位。在许多人刚刚学习计算机语言的时候，大多会被要求写一个算阶乘的程序，而在学习高精度算法的时候，也会写一个计算较大数字阶乘的程序。不过，在实际的运用之中，可能遇到更大数字的阶乘计算和不同要求的阶乘结果，例如：TOJ（同济大学ACM网络题库，http://acm.tongji.edu.cn/problem.php）的1016题——“求N！左边第二位的数字”，这就需要一定的精度思考了。

可是我们通常对于较大数字阶乘的要求是求结果位数或前几位数字，这怎么办呢？

在刘汝佳的《算法艺术与信息学竞赛》一书中，（Page241）介绍了Stirling公式：

其中的～符号是指“同阶”或“相当”，即两者随n增加的大致速度相同，在n较大时，两者极其相近。

这是一个极限的概念（现行教材高二下学期数学内容），属于微分学内容，准确写法为：

但遗憾的是在《算法艺术与信息学竞赛》书中只提供了这个算式，并无他物！

本人近日看到一本数学科普读物——《好玩的数学——不可思议的e》（陈任政著，科学出版社），其中5.12节简介了Stirling逼近近似算阶乘，本人感到好奇，于是对这种算法的具体步骤进行了分析，并研究了它的精确度，故为本文。在2005年8月7日完工之日，笔者上网搜索了一下，找到了一些关于Stirling逼近的文章，偶然地在臺灣亞洲聚合公司蔡永裕《談Stirling公式的改良》（刊自台湾《數學傳播》20卷4期，民国85年12月）一文中找到同感，蔡先生的做法于笔者方向不同，作出来的结果比笔者的算法精确一个数量级左右，惭愧，于是，笔者又再次研究，寻找更好算法，写于本文后部。

 

在1730年，棣莫弗(棣,音Dì)（法国数学家，Abraham De Moiver，1667～1754）发表的《分析杂论》中首先对n!地一个无穷级数展开式给出了近似公式：

但是，现在我们叫这个式子为“Stirling逼近”，中文叫做“斯特林逼近”，这是为什么呢？

因为棣莫弗的朋友苏格兰数学家斯特林(James Stirling,1696~1770)在同年的《微分法或无穷级数的简述》中也给出了等价的级数。

事实上，棣莫弗首先得到的式子是，
但是，他没有把C求出来。而斯特林则利用棣莫弗的发现做了探讨，求出了。

这些式子的来源是一个无穷级数展开式：

其中B₂=1/6，B₄=-1/30，B₆=1/42 … B_2k是雅格布·伯努力数。（具体内容请参见后文介绍）

 

这里介绍一下，还没上高中的同学还没有学到，“乘方”的逆运算有两种：开方和对数。

对于一个幂：，其中a成为底数，n成为指数，b成为幂。已知a和n求b，就是乘方运算；已知b和n，求a，就是开方运算；而已知a和b求n，就是对数运算，写做：，这里n就称为以a为底b的对数（logarithm）。

当底数为10的时候，叫做常用底数，简写做_{e的时候，叫做自然对数，简写做。}；当底数为

至于e的含义：e是重要性仅次于π的数，是极限论的主要内容，具体的说，即：

意思是当n趋向于正的无限大的时候，趋向于e。

e是无理数，即无限不循环小数，也是超越数，即不能满足某个整数系数代数方程的数（不能满足某个整数系数代数方程的数叫做代数数）。

目前e只算到了几千位。

e＝2.718281828459045235360287471352662497757247093…

特别说明的是，在Pascal语言中，exp(n)函数就是e的n次方。

 

另外，有个著名的公式被成为“整个数学中最卓越的公式”：

其中的i为虚数的单位，。来自算术的0、1，来自代数的i，来自几何的π，来自分析学的e，奇妙的组成了一个公式！

这是欧拉（瑞士数学家，Leonhard Euler，1707~1783）发现的！所以称作“欧拉公式”。

不过，真正的欧拉公式是：

那个“最卓越的公式”只是欧拉公式的一个推倒公式。

 

言归正传，由公式

两边同时取e的幂，得
即：

再经过近似等处理（这些处理比较麻烦，而且牵扯到微积分内容）,我们得到了Stirling公式：

注：在本文后部有Stirling公式的推倒过程。

当然，我们可以得到它得更具体形式：

其中的θ是不定的，在（0,1）区间之内。

 

讲到这里，我们有了公式，可以开始计算了。

但是，我们计算什么呢？难道我们要计算N！的值吗？

虽然这个式子比阶乘原始计算式简单，但是实际计算的时候仍然得到的将是上百上千位的数字，而且这个式子毕竟是近似公式，无法真正得到确切得数！

难道我们辛苦的到的式子无用了吗？

答案当然是否定的！我们可以求N！的位数！

 

求位数的方法是取常用对数（以10为底的对数）。那，这是为什么呢？看看下表：

n	n位数
1	0.000000	1
10	1.000000	2
100	2.000000	3
1000	3.000000	4
10000	4.000000	5
100000	5.000000	6
1000000	6.000000	7
10000000	7.000000	8
100000000	8.000000	9

好了！我们知道了n的位数等于，对吗？

不对！不一定是整数，比如，所以，我们得到的公式是：

n的位数＝

其中是取整符号，指不大于n的最大整数，在Pascal语言中为trunc(n)函数。

 

如果我们用Stirling逼近算出n！再算它的位数就太不值得了，这里我们就要运用对数的一些特性来简化公式。

我们两边取常用对数：

进而化简为:

现在我们可以来求值了！

以求1000！的位数为例，

所以1000！的位数为2568位！

我们可以看到，这里的计算复杂度很低，都是O(n)级别的！对于其计算机编程运用来说，计算过程中数字不大不会溢出，取对数后的精确度也可以保证。

这样我们就解决了计算阶乘位数问题！而且可以绝对放心，这个公式在位数方面的准确率是99.9999999999999％以上。(而且这个仅有的可能性也只是从正态性来推测的)

 

用Pascal语言来书写：

 Trunc(0.5*Ln(2*n*3.1415926) /Ln(10) + n*Ln(n/Exp(1)) / Ln(10)) + 1

建议使用分步计算，这样能避免计算过程中的溢出现象。

 

这样，笔者使用批处理计算了几个值：

n	n!位数
1	1
10	7
100	158
1000	2568
10000	35660
100000	456574
1000000	5565709
10000000	65657060
100000000	756570557
1000000000	8565705523

 

由于Longint范围的限制,无法计算再大的数值，但是可以通过使用int64或者extended来解决。

不过，我们有点不甘心，只计算位数难免用途不广，其实，我们可以用来计算n！的前几位！

什么原理呢？

例如计算1000！时，我们得到的数为2567.6046080272230971441871361093945……

而我们从下表中可以看出点东西来:

n
5	0.698970004336019……
50	1.698970004336019……
500	2.698970004336019……
5000	3.698970004336019……

我们可以得知：一个数增大10倍，它的常用对数整数部分将增加1，而小数部分不变。

我们得到的更重要的结果是：一个数的常用对数的小数部分所对应的幂的各位数字（不考虑小数点）与原数各位数字相同。

所以，对于1000！来说:
2567.6046080272230971441871361093945……的小数部分为
0.6046080272230971441871361093945……，
它的10为底的幂为4.0235372577197005393836315765635……，
也就是说1000！这个2568位数的前几位为40235372577197005393836315765635……。

Well！我们可以求出一个阶乘的前几位数了！

但是，不要高兴太早！这里的精度无法保证！

下面让我们来看看精确度方面：

特别说明的是，这里说的精确度是指n!与Stirling逼近公式的精确度，而不是位数计算的精确度，因为位数计算基本上是精确的！

n	逼近值	n！准确值	相对误差
10	3598695.619	3628800	0.008365359
20	2.42279E+18	2.4329E+18	0.004175011
30	2.64517E+32	2.65253E+32	0.002781536
40	8.14E+47	8.16E+47	0.002085461
50	3.04E+64	3.04E+64	0.001668034
60	8.31E+81	8.32E+81	0.001389841
70	1.20E+100	1.20E+100	0.001191177
80	7.15E+118	7.16E+118	0.001042204
90	1.48E+138	1.49E+138	0.000926351
100	9.32E+157	9.33E+157	0.000833678
110	1.59E+178	1.59E+178	0.000757861
120	6.68E+198	6.69E+198	0.000694684
130	6.46E+219	6.47E+219	0.000641230
140	1.35E+241	1.35E+241	0.000595414
150	5.71E+262	5.71E+262	0.000555709
160	4.71E+284	4.71E+284	0.000520968
170	7.25E+306	7.26E+306	0.000490316

 

 

可以看到，本身它的相对误差就很小，并且这个误差是在逐渐减小。

当n＝1000的时候，相对误差只有0.00008333680287333986657587……！

这个误差可以保证我们能够取得阶乘值的前3-4位准确值，但是，还是有点遗憾，感觉不是太好，我们最起码需要7-8位的精确度，可是，我们能做到吗？

可以！

还记得吗？我们曾得到了一个更精确的算式：

（其中的θ是不定的，在（0，1）区间之内。）

 

从这个式子里我们也可以看出准确值和逼近值之比就是

随着n的增大，显然这个值是随n逐渐缩小的！并且是缩得很小，这也符合我们上面表格所体现的内容。

可是，这里的θ是不固定的，要是固定的，我们就可以求出准确值。但是，有没有想看看θ的变化趋势呢？我们用上面算出的相对误差反算θ。

（计算公式为ln（相对误差＋1）×12×n＝θ）

n	θ
10	0.999667612
20	0.999916726
30	0.999962975
40	0.999979170
50	0.999986668
60	0.999990741
70	0.999993198
80	0.999994792
90	0.999995885
100	0.999996667
110	0.999997245
120	0.999997685
130	0.999998028
140	0.999998299
150	0.999998519
160	0.999998698
170	0.999998847
180	0.999998971
190	0.999999077
200	0.999999167

我们惊喜地发现θ竟然十分接近1，而且在逐渐地逼近1，这是个令人兴奋地消息！

实际上，即使是求1的阶乘，θ也会达到0.9727376027，这是一个本身就是一个很“精确”的数字了！当n＝1000时，θ将0.99999996665875876427498746773752，与1的差别只有0.000000033341241235725012532263（约等于3.33412×10^-8）！

如果可以精确到这样，我们就太高兴了！

我们把θ用1带入，然后求值，这次得到的结果出奇的好！

下表是经过θ＝1带入修正的各项指标：

n	修正后逼近值	n！准确值	二者比例
10	3.62881005142693E+06	3.62880000000000E+06	0.999997230103867
20	2.43290285233215E+18	2.43290200817664E+18	0.999999653025394
30	2.65252887092925E+32	2.65252859812191E+32	0.999999897151981
40	8.15915318654567E+47	8.15915283247897E+47	0.999999956604970
50	3.04140938775049E+64	3.04140932017133E+64	0.999999977780315
60	8.32098721974147E+81	8.32098711274139E+81	0.999999987140939
70	1.19785717669724E+100	1.19785716699698E+100	0.999999991901990
80	7.15694574345356E+118	7.15694570462638E+118	0.999999994574895
90	1.48571597014272E+138	1.48571596448176E+138	0.999999996189743
100	9.33262157031762E+157	9.33262154439441E+157	0.999999997222301
110	1.58824554483731E+178	1.58824554152274E+178	0.999999997913062
120	6.68950292420235E+198	6.68950291344912E+198	0.999999998392522
130	6.46685549739670E+219	6.46685548922047E+219	0.999999998735671
140	1.34620124893450E+241	1.34620124757175E+241	0.999999998987707
150	5.71338396114816E+262	5.71338395644585E+262	0.999999999176966
160	4.71472363918940E+284	4.71472363599206E+284	0.999999999321839
170	7.25741561941125E+306	7.25741561530799E+306	0.999999999434611
180	2.00896062594820E+00	2.00896062499134E+00	0.999999999523704
190	9.68032267917558E+00	9.68032267525524E+00	0.999999999595020

可以看到，这里的差别已经很小了！

当n＝1000，二者比例达到了0.999999999997221，这足以保证10位的准确度！

到这里，我们就找到了一个精确度高并且速度快的算法来计算阶乘的前几位！

我们求阶乘前几位的最后公式为

frac(n)为取小数部分

顺便说一下，以上的数据都是用Free Pascal计算的，使用的是Extended格式，由此看来，Extended的精确度也是很高的！

用Pascal语言来书写：

10**frac(0.5*Ln(2*n*3.1415926) / Ln(10) + n * Ln(n / Exp(1)) / Ln(10))*exp(1/12/n)

有个技巧是：在FP中，可以使用a**b来计算a^b，可以不必再用exp(y*ln(x))。

 

笔者希望读者仔细思考，如何书写精度最高，速度最快（尽管速度已经是毫秒级了！）？还请注意数据溢出地情况。

还有，为了输出前几位，需要下点功夫处理一下输出问题。笔者在这里就简略了。

 

别急，我们的“征途”还没完，我们要继续精确化！

 

下面是来自http://mathworld.wolfram.com/StirlingsSeries.html的资料，介绍Stirling’s Series，即“斯特林级数”，也就是Stirling逼近的原始式。比较抽象，读者浏览一下即可。

笔者英语不佳，勉强翻译了一下，便于大家阅读。

Stirling’s Series

斯特林级数

Theasymptotic series for the gamma function is given by

这个Γ函数的渐进级数如下（译者注：Γ为γ的大写，希腊字母，读做“伽马”）

The coefficient of can given explicitly by

的系数可以明确地给出

where is the number of permutations ofnwithk permutation cycles all of which are ≥3(Comtet 1974, p. 267). Another formula for the s is given by the recurrence relation

上面的是一个以k为循环的n的变量，它是始终≥3的(Comtet 1974, p. 267)。另外的一个计算的关系如下

with , then

当，则

where is the double factorial (Borwein and Corless 1999).

这里的的意思是双阶乘(Borwein and Corless 1999).

（译者注：把阶乘的定义引申，定义N!! = N*(N-2)*(N-4)*…，若N为偶数，则乘至2，反之，则乘至1，而0!! = 0。我们称之为双阶乘(Double Factorial)）

The series for is obtained by adding an additional factor ofx,

级数是由x+1的Γ函数获得，

The expansion of is what is usually called Stirling’s series. It is given by the simple analytic expression

的展开式通常被叫做斯特林级数。它简单地分析表示为,

where  is aBernoulli number. Interestingly, while the numerators in this expansion are the same as those of for the first several hundred terms, they differ at n=574, 1185, 1240, 1269, 1376, 1906, 1910, … , with the corresponding ratios being 37, 103, 37, 59, 131, 37, 67, …

这里地是伯努力数。有趣的是，当n每增加数百后，会出现重复，比如当n＝574, 1185, 1240, 1269, 1376, 1906 , 1910 , … 时，对应的是37, 103, 37, 59, 131, 37, 67, …

 

对于以上内容，单就本文所讨论的主题来说，没有太大用途，许多人在用Stirling公式计算大数阶乘的时候（注意，他们是直接计算阶乘近似值，而笔者是通过常用对数反算近似值），常常不使用“Stirling逼近”而直接使用“Stirling级数展开式”，这样主要是因为他们注意到了“Stirling逼近”简单式的误差过大，转而使用10－100项的“Stirling级数展开式”。在本文中，笔者使用“Stirling逼近”的“精确式”，采用修正的方法求近似值，已经取得了不亚于使用100项的“Stirling级数展开式”的精确度，并且避免了阶乘数值的溢出。

笔者在上文也说过，笔者看了台湾蔡永裕先生的《談Stirling公式的改良》一文，感觉非常有水平，笔者有时很有疑问，台湾地区的计算机学、数学等科学的发展水平还是比较高的！经常性的笔者搜索数学、计算机学的内容都会搜到许多台湾网站的内容，可能还有一个原因就是台湾地区的计算机普及率较高，资料上网率较高。

这里两个网址：

臺灣“中央研究院”數學研究所（数学研究所）http://www.math.sinica.edu.tw/

《數學傳播》杂志（《数学传播》）http://www.math.sinica.edu.tw/media/default.jsp

读者能看得顺繁体字更好，如果看不大习惯，就用一些软件来“转换”一下。

再次言归正传，蔡永裕先生的原理与笔者基本相同，都是对Stirling逼近公式进行修正，蔡先生文中联想到公式：

于是设e的渐近相等值E，将Stirling公式变为（笔者注：即≈）

反算得渐近于1，于是设

其中F_n为修正参数，则导出

然后反算得数据表格。继而欲求F_n的表达式，经过试验，选择了

得到了Stirling公式的修正版：

其常用对数形式为：

这样一来，精确度提高了很多，当计算1000！时，蔡先生的算法误差仅有-2.971E-13，而如果使用原始Stirling式的误差为-8.33299E-05，笔者之前的算法误差是1.118E-12，略逊于蔡式算法，于是笔者思考了一下，使用二次修正的方法来实现精确化。

方法如下：

对于公式：

因为θ接近于1，则令，f(n)为修正函数。则

为了寻找f(n)的式子，从简单的一次函数试起，我们先试一试f(n)/n，发现竟然是等差数列，在除以n后，得到的是一个常量！

n	θ	f(n)	f(n)/n	f(n)/n2
50	0.999986668189609	75008.56753	1500.171351	30.00342701
100	0.999996666761655	300008.5492	3000.085492	30.00085492
150	0.999998518536300	675008.1019	4500.054013	30.00036009
200	0.999999166673422	1200009.727	6000.048637	30.00024319
250	0.999999466670049	1875011.893	7500.047571	30.00019028
300	0.999999629630836	2700008.792	9000.029307	30.00009769
350	0.999999727877187	3674811.34	10499.46097	29.99845991
400	0.999999791661586	4799882.935	11999.70734	29.99926834
450	0.999999835405298	6075529.694	13501.1771	30.00261577
500	0.999999866704792	7502145.139	15004.29028	30.00858056
550	0.999999889796665	9074135.523	16498.42822	29.99714222
600	0.999999907419129	10801367.44	18002.27906	30.00379843
650	0.999999921104972	12675069.96	19500.10763	30.00016558
700	0.999999931990204	14703764.09	21005.37728	30.00768183
750	0.999999940767808	16882711.46	22510.28195	30.01370927
800	0.999999947926410	19203592.46	24004.49057	30.00561321
850	0.999999953865914	21675947.14	25501.11429	30.00131093
900	0.999999958850112	24301402.95	27001.55883	30.00173203
950	0.999999963096340	27097582.94	28523.77151	30.02502264
1000	0.999999966659766	29993790.67	29993.79067	29.99379067

 

显然，它们都与30相近；而且，我们完全可以认为，这里的误差是由计算误差引起的！

 

于是，我们得到f(n)＝30n²关系式。

继而，有

“前几位”公式：

这样一来

n	二次修正版逼近值 科学计数法系数	n！准确值 科学计数法系数	相对误差
50	3.04140932016361	3.04140932017133	-2.5383029012E-12
100	9.33262154439367	9.33262154439441	-7.9380946261E-14
150	5.71338395644579	5.71338395644585	-1.0547118734E-14
200	7.88657867364788	7.88657867364790	-2.5535129566E-15

看！仅仅n＝200的时候，误差就小于!

不过，由于毕竟f(n)＝30n²是有误差的，所以误差不会一直减少，而会波动，正如上面的求f(n)/n²的表格，它的值是波动的。

这是因为：我们不可能用固定的多项式来表示出对数型变化！

但我们把误差降到了最小，当n＝1000时，
逼近值4.0238726007709361277668E+2568与准确值4.0238726007709377354370E+2568的误差仅有-3.9953306821471308041868495761274E-16

事实上，在高等数学里，根据Taylor展式可以算得：

看似我们属于“碰对了”，其实这就是“数学实验”的魅力！

 

到此为止，我们可以说获得了成功！！！

 

在编程方面，注意点很多，主要还是溢出的问题，比如1/（360*n*n*n）对于较大的可能溢出，而写成1/360/n/n/n就可以避免。

exp(frac(0.5*Ln(2*n*3.14159265358979323)/Ln(10)+n*Ln(n/Exp(1))/Ln(10))*ln(10))*exp(1/12/n-1/360/n/n)

 

以上内容是笔者看书时偶尔思考到的，并认真得进行了思考和实验，具体地试验比较，这种做法叫做“数学实验”。

《数学实验》是在我国高等学校中新开设的一门课程。现在还处于试点和摸索阶段，有许多不同的想法和作法。课程目的,是使学生掌握数学实验的基本思想和方法，即不把数学看成先验的逻辑体系，而是把它视为一门“实验科学”，从问题出发，借助计算机，通过学生亲自设计和动手，体验解决问题的过程，从实验中去学习、探索和发现数学规律。既然是实验课而不是理论课，最重要的就是要让学生自己动手，自己借助于计算机去“折腾”数学，在“折腾”的过程中去学习，去观察，去探索，去发现，而不是由老师教他们多少内容。既不是由老师教理论，主要的也不是由老师去教计算机技术或教算法。不着意追求内容的系统性、完整性。而着眼于激发学生自己动手和探索的兴趣。

数学实验可以包括两部分主要内容：第一部分是基础部分，围绕高等数学的基本内容，让学生充分利用计算机及软件（比较有名的是Mathematica）的数值功能和图形功能展示基本概念与结论，去体验如何发现、总结和应用数学规律。另一部分是高级部分，以高等数学为中心向边缘学科发散，可涉及到微分几何，数值方法，数理统计，图论与组合，微分方程，运筹与优化等，也可涉及到现代新兴的学科和方向，如分形、混沌等。这部分的内容可以是新的，但不必强调完整性，教师介绍一点主要的思想，提出问题和任务，让学生尝试通过自己动手和观察实验结果去发现和总结其中的规律。即使总结不出来也没有关系，留待将来再学，有兴趣的可以自己去找参考书寻找答案。

笔者写本文，一来总结自己所想，二来抛砖引玉，希望大家能在数学中寻找灵感，并优化使之适用于计算机编程，这才是算法艺术！

 

共11641字

写于：2005年8月6日～8日

江苏·赣榆

 

参考文献：

《好玩的数学——不可思议的e》（陈任政著，科学出版社，2005）；

《談Stirling公式的改良》（蔡永裕，臺灣亞洲聚合公司，刊自台湾《數學傳播》20卷4期，民国85年12月－公元1996年12月）；
pdf文件下载：
http://www.math.sinica.edu.tw/math_media/pdf.php?m_file=ZDIwNC8yMDQwNA==

《談Stirling公式》(蔡聰明,載於數學傳播第十七卷第二期,作者當時任教於台大數學系)；
http://episte.math.ntu.edu.tw/articles/mm/mm_17_2_05/

清华大学在线学习－－《组合数学》之（1.3节Stirling近似公式）；
http://www.cs.cityu.edu.hk/~luoyan/mirror/tsinghua/combinemaths/1/1_3.htm

Stirling级数http://mathworld.wolfram.com/StirlingsSeries.html

入门篇之二

在《大数阶乘之计算从入门到精通―入门篇之一》中，我们给出一个计算阶乘的程序，它采用char型数组存贮大数，1个元素表示1位十进制数字，在计算时，一次乘法可计算一位数字和一个整数的乘积。该算法具有简单直观的优点，但缺点也是明显的，速度不快，占用内存空间也较多，本文将给出一个改后的程序，有效的克服了这些缺点。

学过80×86汇编的人都知道，8086/8088的CPU可对两个16比特的数相乘，其结果为32比特,80386及其后的32位CPU可对两个32比特的数相乘，结果为64比特（以下写作bit）。8086 CPU等16位CPU已完全淘汰，这是不去讨论它。在32位c语言编译器中，unsigned long(DWORD)型变量可以表示一个32bit的整数，unsigned short(WORD)型变量可表示一个16bit的整数。两个65535以内的数相乘，其结果完全可以存贮在一个unsigned long变量中。另外，在好多32位编译器中，也提供了64bit的整数类型（如在VC中，unsigned __int64可表示一个64bit的整数,在GCC中，long long可表示一个64位的整数）。同理两个40亿以内的数相乘，其结果可以用一个unsigned __int64 型的变量来存储。让一个具有一次可计算两个32bit数乘法能力的CPU一次只计算1个1位10进制数和一个整数的乘法，实在是一种浪费。下面我们提出两种大数的表示法和运算方法。

第一种方法：用WORD型数组表示大数，用DWORD型变量表示两个WORD型变量的乘积。数组的每个元素表示4位十进制数。在运算时，从这个数的最后一个元素开始，依次乘以当前乘数并加上上次的进位，其和的低4位数依然存在原位置，高几位向前进位。当乘数i小于42万时，其乘积加上进位可以用一个DWORD型变量表示，故这个程序可以计算上到42万的阶乘，当计算42万的阶乘时，占用内存空间小于1.1兆字节。至于速度，在计算1000/10000的阶乘时，在迅驰1.7G电脑约需0.015/0.86秒。

 

#include “stdlib.h”

#include “stdio.h”

#include “math.h”

 

#define PI 3.1415926535897932384626433832795

#define RAD 10000

typedef unsigned long DWORD;

typedef unsigned short WORD;

//用stirling公式估算结果长度,稍微算得大一点

DWORD calcResultLen(DWORD n,DWORD rad)

{

    double r=0.5*log(2*PI) + (n+0.5)*log(n)-n;

   return (DWORD)(r/log(rad)+2);

}

 

void calcFac1(DWORD n)

{

    DWORD i,carry,prod,len;

    WORD *buff,*pHead,*pTail,*p;

if (n==0)        

      { printf(“%d!=1”,n); return; }

 //—计算并分配所需的存储空间

 len=calcResultLen(n,RAD); 

 

     buff=(WORD*)malloc( sizeof(WORD)*len);

 

     if (buff==NULL)

             return ;

 //以下代码计算n!

    pHead=pTail=buff+len-1;

    for (*pTail=1,i=2;i<=n;i++)

    {

for (carry=0,p=pTail;p>=pHead;p–)

                  {

                     prod=(DWORD)(*p) * i +carry;

                     *p=(WORD)(prod % RAD);

                      carry=prod / RAD;

                  }

      while (carry>0)

                 {

                          pHead–;

                          *pHead=(WORD)(carry % RAD);

                          carry /= RAD;

                  }

    }

  //显示计算结果

  printf(“%d!=%d”,n,*pHead); 

   for (p=pHead+1;p<=pTail;p++)

printf(“%04d”,*p);

     printf(“/n”);

   free(buff);//释放分配的内存

}

int main(int argc, char* argv[])

{

DWORD n;

printf(“please input n:”);

scanf(“%d”,&n);

calcFac1(n);

return 0;

}

 

第二种方法：用DWORD型数组表示大数，用unsigned __int64 表示两个DWORD型变量的乘积。数组的每个元素表示9位十进制数。在运算时，从这个数的最后一个元素开始，依次乘以当前乘数i(i=1..n)并加上上次的进位,其和的低9位数依然存在原位置，高几位向前进位。从算法上讲，这个程序能够计算到40亿的阶乘，在实际计算过程中，仅受限于内存的大小。至于速度，比前一个程序要慢一些，原因在于unsigned __int64的除法较慢。我们将在下一篇文章给出解决方法，下面是采用该方法计算阶乘的代码。

#define TEN9 1000000000

void calcFac2(DWORD n)

{

     DWORD *buff,*pHead,*pTail,*p;

     DWORD t,i,len;

     UINT64 carry,prod;

   

     if (n==0)

     { printf(“%d!=1”,n); return; }

 //—计算并分配所需的存储空间

     t=GetTickCount();

     len=calcResultLen(n,TEN9);

     buff=(DWORD*)malloc( sizeof(DWORD)*len);

     if (buff==NULL)

             return ;

 //以下代码计算n!

     pHead=pTail=buff+len-1;

     for (*pTail=1,i=2;i<=n;i++)

     {

                  for (carry=0,p=pTail;p>=pHead;p–)

                  {

                        prod=(UINT64)(*p) * (UINT64)i +carry;

                        *p=(DWORD)(prod % TEN9);

                        carry=prod / TEN9;

                  }

                  while (carry>0)

                  {

                          pHead–;

                          *pHead=(DWORD)(carry % TEN9);

                          carry /= TEN9;

                  }

     }

     t=GetTickCount()-t;

//显示计算结果 

     printf(“It take %d ms/n”,t);

     printf(“%d!=%d”,n,*pHead);

     for (p=pHead+1;p<=pTail;p++)

       printf(“%09d”,*p);

     printf(“/n”);

    free(buff);//释放分配的内存

}

 入门篇之三汇编的威力

在上一篇文章《大数阶乘之计算从入门到精通–入门篇之二》中，我们给出两个计算大数阶乘的程序，其中第2个程序由于用到64位整数的除法，速度反而更慢。在本文中，我们采用在C语言中嵌入汇编代码的方法，改进瓶颈部分，使计算速度提高到原先3倍多。

我们首先看一下计算大数阶乘的核心代码(见下)，可以看到，在每次循环中，需要计算1次64位的乘法，1次64位的加法，2次64位的除法(求余视为除法)。我们知道，除法指令是慢于乘法指令的，对于64位的除法更是如此。在vc中，两个64位数的除法是调aulldiv函数来实现的，两个64位数的求余运算是调用aullrem来实现的。通过分析这两个函数的源代码(汇编代码)得知，在做除法运算时，首先检查除数，如果它小于2的32次方,则需两次除法以得到一个64位商，如果除数大于等于2³²，运算将更为复杂。同样在做求余运算时，如果除数小于2³²，为了得到一个32位的余数，也需2次除法。在我们这个例子中，除数为1000000000，小于2³²，因此，这段代码需4次除法。

for (carry=0,p=pTail;p>=pHead;p–)

{

     prod=(UINT64)(*p) * (UINT64)i +carry;

     *p=(DWORD)(prod % TEN9);

         carry=prod / TEN9;

}

 

我们注意到，在这段代码中，在进行除法运算时，其商总是小于2的32次方,因此，这个64位数的除法和求余运算可以用一条除法指令来实现。下面我们用C函数中嵌入汇编代码的方法，执行一次除法指令同时得到商和余数。函数原形为：DWORD Div_TEN9_2 (UINT64 x,DWORD *pRemainder );这个函数返加x除以1000000000的商，除数存入pRemainder。下面是函数Div_TEN9_2和计算阶乘的代码，用C中嵌入式汇编实现。关于C代码中嵌入汇编的用法，详见MSDN。

 inline DWORD Div_TEN9_2(UINT64 x,DWORD *pRemainder )

{

         _asm

         {

                  mov eax,dword ptr [x]  // low DWORD

                  mov edx,dword ptr [x+4]// high DWORD

                 

                  mov ebx,TEN9

                  div ebx

                  mov ebx,pRemainder

                  mov [ebx],edx                // remainder-> *remainder

                                                    // eax, return value

         }

}

void calcFac2(DWORD n)

{

     DWORD *buff,*pHead,*pTail,*p;

     DWORD t,i,len,carry;

     UINT64 prod;

   

     if (n==0)

     { printf(“%d!=1”,n); return; }

 //—计算并分配所需的存储空间

     t=GetTickCount();

        

     len=calcResultLen(n,TEN9);

     buff=(DWORD*)malloc( sizeof(DWORD)*len);

     if (buff==NULL)

             return ;

 //以下代码计算n!

     pHead=pTail=buff+len-1;

     for (*pTail=1,i=2;i<=n;i++)

     {

                  for (carry=0,p=pTail;p>=pHead;p–)

                  {

                      prod=(UINT64)(*p) * (UINT64)i +(UINT64)carry;

                      carry=Div_TEN9_2(prod,p );

                  }

                 

                  while (carry>0)

                  {

                          pHead–;

                          *pHead=(DWORD)(carry % TEN9);

                          carry /= TEN9;

                  }

       }

  t=GetTickCount()-t;

 

     //显示计算结果 

         printf(“It take %d ms/n”,t);

     printf(“%d!=%d”,n,*pHead);

     for (p=pHead+1;p<=pTail;p++)

            printf(“%09d”,*p);

     printf(“/n”);

 free(buff);                  //释放分配的内存

}

注意，本文题名虽为汇编的威力，用汇编语言并不总是那么有效，一般情况下，将关键代码用汇编改写后，性能提升的幅度并不像上面的例子那么明显，可能至多提高30%，本程序是特例。

 

最后的改进：如果我们分析一下这几个计算阶乘的函数，就会发现，计算阶乘其实际上是一个二重循环，内循环部分计算出(i-1)! * i, 外循环则依次计算2!,3!，4!，直到n!,假如们己计算出来r=(i-1)!,可否先算出 prod= i*(i+1)* …m, 使得i*(i+1)* …刚好小于2^32,而i*(i+1)* …m*(m+1)则 >=2^32, 再计算r * prod,如此一来，可减少外循环的次数，从而提高速度。理论和测试结果都表明，当计算30000以下的阶乘时，速度可提高1倍以上。下面给出代码。

void calcFac3(DWORD n)

{

       DWORD *buff,*pHead,*pTail,*p;

       DWORD t,i,len,carry;

       UINT64 prod;

   

        if (n==0)

        { printf(“%d!=1”,n); return; }

 //—计算并分配所需的存储空间

        t=GetTickCount();

  

        len=calcResultLen(n,TEN9);

        buff=(DWORD*)malloc( sizeof(DWORD)*len);

        if (buff==NULL)

            return ;

   //以下代码计算n!

                pHead=pTail=buff+len-1;

        for (*pTail=1,i=2;i+15<n;)

        {

              UINT64 t=i++;

               while (t<4294967296I64)

               {

                      t *= (UINT64)i;                 i++;

               }

               i–;

               t/=i;

          

               for (carry=0,p=pTail;p>=pHead;p–)

               {

                       prod=(UINT64)(*p) * t +(UINT64)carry;

                       carry=Div_TEN9_2(prod,p );

               }

          

               while (carry>0)

               {

                      pHead–;

                      *pHead=(DWORD)(carry % TEN9);

                       carry /= TEN9;

               }

        }

  

        for (;i<=n;i++)

        {

                    for (carry=0,p=pTail;p>=pHead;p–)

                    {

                             prod=(UINT64)(*p) * (UINT64)i +(UINT64)carry;

                             carry=Div_TEN9_2(prod,p );

                    }

          

                    while (carry>0)

                    {

                             pHead–;

                             *pHead=(DWORD)(carry % TEN9);

                             carry /= TEN9;

                    }

        }

  

      printf(“It take %d ms/n”, GetTickCount()-t);

   //显示计算结果

     printf(“%d!=%d”,n,*pHead);

     for (p=pHead+1;p<=pTail;p++)

           printf(“%09d”,*p);

     printf(“/n”);

 free(buff);//释放分配的内存

}

求N!的高精度算法

 

本文是张一飞2001年写的论文，原文可从http://oibh.kuye.cn/download/thesis/thesis2001_zhangyifei.zip处下载

 求N!的高精度算法

本文中的算法主要针对Pascal语言

这篇文章的内容

你了解高精度吗？

你曾经使用过哪些数据结构？

你仔细思考过如何优化算法吗？

在这里，你将看到怎样成倍提速求N!的高精度算法

Pascal中的标准整数类型

数据类型	值域
Shortint	-128～127
Byte	0～ 255
Integer	-32768～ 32768
Word	0～ 65535
LongInt	-2147483648～2147483647
Comp	-9.2e18～9.2e18

Comp虽然属于实型，实际上是一个64位的整数

高精度算法的基本思想

Pascal中的标准整数类型最多只能处理在-263～263之间的整数。如果要支持更大的整数运算，就需要使用高精度

高精度算法的基本思想，就是将无法直接处理的大整数，分割成若干可以直接处理的小整数段，把对大整数的处理转化为对这些小整数段的处理

数据结构的选择

每个小整数段保留尽量多的位

使用Comp类型

采用二进制表示法

 

每个小整数段保留尽量多的位

一个例子：计算两个15位数的和

Ø方法一

•分为15个小整数段，每段都是1位数，需要15次1位数加法

Ø方法二

•分为5个小整数段，每段都是3位数，需要5次3位数加法

Ø方法三

•Comp类型可以直接处理15位的整数，故1次加法就可以了

Ø比较

•用Integer计算1位数的加法和3位数的加法是一样快的

•故方法二比方法一效率高

•虽然对Comp的操作要比Integer慢，但加法次数却大大减少

•实践证明，方法三比方法二更快

使用Comp类型

高精度运算中，每个小整数段可以用Comp类型表示

Comp有效数位为19～20位

求两个高精度数的和，每个整数段可以保留17位

求高精度数与不超过m位整数的积，每个整数段可以保留18–m位

求两个高精度数的积，每个整数段可以保留9位

如果每个小整数段保留k位十进制数，实际上可以认为其只保存了1位10^k进制数，简称为高进制数，称1位高进制数为单精度数

采用二进制表示法

采用二进制表示，运算过程中时空效率都会有所提高，但题目一般需要以十进制输出结果，所以还要一个很耗时的进制转换过程。因此这种方法竞赛中一般不采用，也不在本文讨论之列.

算法的优化

高精度乘法的复杂度分析

连乘的复杂度分析

设置缓存

分解质因数求阶乘

二分法求乘幂

分解质因数后的调整

高精度乘法的复杂度分析

计算n位高进制数与m位高进制数的积

Ø需要n*m次乘法

Ø积可能是n+m–1或n+m位高进制数

连乘的复杂度分析（1）

一个例子：计算5*6*7*8

Ø方法一：顺序连乘

•5*6=30，1*1=1次乘法

•30*7=210，2*1=2次乘法

•210*8=1680，3*1=3次乘法  共6次乘法

Ø方法二：非顺序连乘

•5*6=30，1*1=1次乘法

•7*8=56，1*1= 1次乘法

•30*56=1680，2*2=4次乘法   共6次乘法

连乘的复杂度分析（2）

若“n位数*m位数=n+m位数”，则n个单精度数，无论以何种顺序相乘，乘法次数一定为n(n-1)/2次

Ø证明：

•设F(n)表示乘法次数，则F(1)=0，满足题设

•设k<n时，F(k)=k(k-1)/2，现在计算F(n)

•设最后一次乘法计算为“k位数*(n-k)位数”，则

•F(n)=F(k)+F(n-k)+k (n-k)=n(n-1)/2（与k的选择无关）

设置缓存（1）

一个例子：计算9*8*3*2

Ø方法一：顺序连乘

•9*8=72，1*1=1次乘法

•72*3=216，2*1=2次乘法

•216*2=432，3*1=3次乘法

Ø方法二：非顺序连乘

•9*8=72，1*1=1次乘法

•3*2=6，1*1=1次乘法

•72*6=432，2*1=2次乘法

共6次乘法

 

特点：n位数*m位数可能是n+m-1位数

设置缓存（2）

考虑k+t个单精度数相乘a1*a2*…*ak*ak+1*…*ak+t

Ø设a1*a2*…*ak结果为m位高进制数（假设已经算出）

Øak+1*…*ak+t结果为1位高进制数

Ø若顺序相乘，需要t次“m位数*1位数”，共mt次乘法

Ø可以先计算ak+1*…*ak+t，再一起乘，只需要m+t次乘法

在设置了缓存的前提下，计算m个单精度数的积，如果结果为n位数，则乘法次数约为n(n–1)/2次，与m关系不大 

–设S=a1a2… am，S是n位高进制数
–可以把乘法的过程近似看做，先将这m个数分为n组，每组的积仍然是一个单精度数，最后计算后面这n个数的积。时间主要集中在求最后n个数的积上，这时基本上满足“n位数*m位数=n+m位数”，故乘法次数可近似的看做n(n-1)/2次

设置缓存（3）

缓存的大小

Ø设所选标准数据类型最大可以直接处理t位十进制数

Ø设缓存为k位十进制数，每个小整数段保存t–k位十进制数

Ø设最后结果为n位十进制数，则乘法次数约为

Øk/(n–k) ∑_(i=1..n/k)i=(n+k)n/(2k(t–k))，其中k远小于n

Ø要乘法次数最少，只需k (t–k)最大，这时k=t/2

Ø因此，缓存的大小与每个小整数段大小一样时，效率最高

Ø故在一般的连乘运算中，可以用Comp作为基本整数类型，每个小整数段为9位十进制数，缓存也是9位十进制数

分解质因数求阶乘

例：10!=2⁸*3⁴*5²*7

Øn!分解质因数的复杂度远小于nlogn，可以忽略不计

Ø与普通算法相比，分解质因数后，虽然因子个数m变多了，但结果的位数n没有变，只要使用了缓存，乘法次数还是约为n(n-1)/2次

Ø因此，分解质因数不会变慢（这也可以通过实践来说明）

Ø分解质因数之后，出现了大量求乘幂的运算，我们可以优化求乘幂的算法。这样，分解质因数的好处就体现出来了

二分法求乘幂

二分法求乘幂，即：

Øa²ⁿ⁺¹=a²ⁿ*a

Øa²ⁿ=(aⁿ)²

Ø其中，a是单精度数

复杂度分析

Ø假定n位数与m位数的积是n+m位数

Ø设用二分法计算aⁿ需要F(n)次乘法

ØF(2n)=F(n)+n²，F(1)=0

Ø设n=2^k，则有F(n)=F(2^k)=∑_(i=0..k–1)4ⁱ=(4^k–1)/3=(n²–1)/3

与连乘的比较

Ø用连乘需要n(n-1)/2次乘法，二分法需要(n²–1)/3

Ø连乘比二分法耗时仅多50%

Ø采用二分法，复杂度没有从n²降到nlogn

二分法求乘幂之优化平方算法

怎样优化

Ø(a+b)²=a²+2ab+b²

Ø例：12345²=123²*10000+45²+2*123*45*100

Ø把一个n位数分为一个t位数和一个n-t位数，再求平方

怎样分

Ø设求n位数的平方需要F(n)次乘法

ØF(n)=F(t)+F(n-t)+t(n-t)，F(1)=1

Ø用数学归纳法，可证明F(n)恒等于n(n+1)/2

Ø所以，无论怎样分，效率都是一样

Ø将n位数分为一个1位数和n–1位数，这样处理比较方便

二分法求乘幂之复杂度分析

复杂度分析

Ø前面已经求出F(n)=n(n+1)/2，下面换一个角度来处理

ØS²=(∑_(0≤i<n)a_i10ⁱ)²=∑_(0≤i<n)a_i²10²ⁱ+2∑_(0≤i<j<n)a_ia_j10^i+j

Ø一共做了n+C(n,2)=n(n+1)/2次乘法运算

Ø普通算法需要n²次乘法，比改进后的慢1倍

改进求乘幂的算法

Ø如果在用改进后的方法求平方，则用二分法求乘幂，需要(n+4)(n–1)/6次乘法，约是连乘算法n(n–1)/2的三分之一

分解质因数后的调整（1）

为什么要调整

Ø计算S=2¹¹3¹⁰，可以先算2¹¹，再算3¹⁰，最后求它们的积

Ø也可以根据S=2¹¹3¹⁰=6¹⁰*2，先算6¹⁰，再乘以 2即可

Ø两种算法的效率是不同的

分解质因数后的调整（2）

什么时候调整

Ø计算S=a^x+kb^x=(ab)^xa^k

Ø当k<xlog_ab时，采用(ab)^xa^k比较好，否则采用a^x+kb^x更快

Ø证明：

•可以先计算两种算法的乘法次数，再解不等式，就可以得到结论

•也可以换一个角度来分析。其实，两种算法主要差别在最后一步求积上。由于两种方法，积的位数都是一样的，所以两个因数的差越大，乘法次数就越小

•∴当a^xb^x–a^k>a^x+k–b^x时，选用(ab)^xa^k，反之，则采用a^x+kb^x。

•∴a^xb^x–a^k>a^x+k–b^x

•∴(b^x–a^k)(a^x+1)>0

•∴b^x>a^k

•这时k<xlog_ab

总结

内容小结

Ø用Comp作为每个小整数段的基本整数类型

Ø采用二进制优化算法

Ø高精度连乘时缓存和缓存的设置

Ø改进的求平方算法

Ø二分法求乘幂

Ø分解质因数法求阶乘以及分解质因数后的调整

应用

Ø高精度求乘幂（平方）

Ø高精度求连乘（阶乘）

Ø高精度求排列组合

结束语

求N!的高精度算法本身并不难，但我们仍然可以从多种角度对它进行优化。

其实，很多经典算法都有优化的余地。我们自己编写的一些程序也不例外。只要用心去优化，说不准你就想出更好的算法来了。

也许你认为本文中的优化毫无价值。确实是这样，竞赛中对高精度的要求很低，根本不需要优化。而我以高精度算法为例，不过想谈谈如何优化一个算法。我想说明的只有一点：
算法是可以优化
的。