大数阶乘算法.doc

《大数阶乘算法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、*************************************(1)****************************************************     假如需要计算n+16的阶乘，n+16接近10000，已经求得n!（共有m个单元），（每个单元用一个long数表示，表示1-）  第一种算法（传统算法）计算(n+1)!  需要  m次乘法，  m次加法(加法速度较快,可以不予考虑,下同)，m次求余（求本位)，m次除法(求进位），结果为m+1的单元计算(n+2)!  需要  m+1次乘法，  m+1

2、次求余，  m+1次除法,  结果为m+1个单元计算(n+3)!  需要  m+1次乘法，  m+1次求余  ，m+1次除法  ，结果为m+2个单元计算(n+4)!  需要  m+2次乘法，  m+2次求余  ，m+2次除法  ，结果为m+2个单元计算(n+5)!  需要  m+2次乘法，  m+2次求余  ，m+2次除法  ，结果为m+3个单元计算(n+6)!  ...计算(n+7)!  ...计算(n+8)!  ...计算(n+9)!  ...计算(n+10)!  ...计算(n+11)!  ...计算(n+12)!  ...计算(

3、n+13)!  ...计算(n+14)!  需要  m+7次乘法，m+7次求余  ，m+7次除法  ，结果为m+7个单元计算(n+15)!  需要  m+7次乘法，m+7次求余  ，m+7次除法  ，结果为m+8个单元计算(n+16)!  需要  m+8次乘法，m+8次求余  ，m+8次除法  ，结果为m+8个单元该算法的复杂度：共需:m+(m+8)+(m+1+m+7)*7=16m+64次乘法，16m+64次求余，16m+64次除法  第二种算法：1.将n+1  与n+2  相乘,将n+3  与n+4  相乘,将n+5  与n+6...

4、n+15与n+16,得到8个数，仍然叫做n1,n2,n3,n4,n5,n6,n7,n82.  n1  与  n2相乘，结果叫做p2，结果为2个单元，需要1次乘法。       p2  与  n3相乘，结果叫做p3，需要2次乘法，1次加法(加法速度快，下面省略），2次除法，2次求余       p3  与  n4相乘，结果叫做p4，需要3次乘法，3次除法，3次求余       p4  与  n4相乘，结果叫做p5，需要4次乘法，4次除法，4次求余       p5  与  n6相乘，结果叫做p6，需要5次乘法，5次除法，5次求余     

5、  p6  与  n7相乘，结果叫做p7，需要6次乘法，6次除法，6次求余       p7  与  n8相乘，结果叫做p8，结果为8个单元，需要7次乘法，7次除法，7次求余       这一过程的复杂度为（1+2+3+...+7)共计28次乘法，28次求余，28次除法。3.将  n!（m个单元)  与p8(8个单元)相乘，需要m*8次乘法，m次除法，m次求余，（注意不是m*8次求余，m*8次除法,原因请大家思考)该算法的复杂度为  8m次乘法，m次求余，m次除法。假定求余运算和除法运算和乘法的复杂度相同，则第第一种算法需要48m+19

6、2次乘法，而第2种运算需要10m+84次乘法，当m很大时，第二种算法的速度是第一种算法的4.8倍。       第二种算法表明，在计算阶乘时，通常的方法（先计算出n的阶乘，再用一位数乘以多位数的方法计算(n+1)的阶乘，再计算n+2的阶乘）不是最优的，更优化的算法是，计算出相邻的几个数的积（称之为部分积），用  部分积  乘以  部分积  的这种多位数  乘以  多位数的算法来计算。如果两个多位数均为n位，使用FFT算法可以将乘法运算的速度  由  n*n  提高  n*log2(n),当n很大时，FFT算法的速度大大快与常规算法。#i

7、nclude  #include  #include  #define  PI    3.#define  E2.#define  TEN9    typedef  unsigned  __int64  UINT64;typedef  unsigned  long  DWORD;int  calcResultLen(DWORD  n){   return  log10(2*PI*(double)n)/2  +  n  *    log10((double)n/E)+2;}void  

8、printfResult(DWORD  *buff,int  buffLen){   DWORD  *p=buff;   while  (  *p==0)p++;   printf("n!=");