大数阶乘算法.doc

*(1)* 假如需要计算n+16的阶乘，n+16接近10000，已经求得n!（共有m个单元），（每个单元用一个long数表示，表示1-100000000） 第一种算法（传统算法） 计算(n+1)! 需要 m次乘法， m次加法(加法速度较快,可以不予考虑,下同)，m次求余（求本位)，m次除法(求进位），结果为m+1的单元 计算(n+2)! 需要 m+1次乘法， m+1次求余， 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)! . 计算(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.n+15与n+16,得到8个数，仍然叫做n1,n2,n3,n4,n5,n6,n7,n8 2. 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次求余 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+192次乘法， 而第2种运算需要10m+84次乘法，当m很大时，第二种算法的速度是第一种算法的4.8倍。 第二种算法表明，在计算阶乘时，通常的方法（先计算出n的阶乘，再用一位数乘以多位数的方法计算(n+1)的阶乘，再计算n+2的阶乘）不是最优的，更优化的算法是，计算出相邻的几个数的积（称之为部分积），用 部分积 乘以 部分积 的这种多位数 乘以 多位数的算法来计算。如果两个多位数均为n位，使用FFT算法可以将乘法运算的速度 由 n*n 提高 n*log2(n),当n很大时，FFT算法的速度大大快与常规算法。#include #include #include #define PI 3.1415926535897932384626433832795#define E 2.7182818284590452353602874713527#define TEN9 1000000000typedef 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 printfResult(DWORD *buff,int buffLen) DWORD *p=buff; while ( *p=0) p+; printf(nn!=n); for ( int i=0;ibuffLen;i+) if (i=0) printf(%9d ,pi); else printf(%09d ,pi); if (i % 8=7) printf(n); printf(n);void calcFac(DWORD *buff, int buffLen,DWORD n) int len=1; DWORD carry,*p,*pEnd,*pBeg; unsigned _int64 prod; memset(buff,0, sizeof(DWORD)*buffLen); pBeg=buff+buffLen-1; *pBeg=1; for (DWORD i=2;ipEnd;p-) prod= (UINT64)(*p) * (UINT64)i + (UINT64)carry; *p= prod % TEN9; carry=prod / TEN9; if (carry0) *(pBeg-len)=carry; len+; int main(int argc, char* argv) DWORD n=1; printf(n=?); scanf(%d,&n); int buffLen=(calcResultLen(n)+8) / 9; DWORD *buff=new DWORDbuffLen; calcFac(buff, buffLen, n); printfResult(buff,buffLen); delete buff; return 0;*(2)*用数组的方法解决大数、巨数的阶乘结果越界的问题。具体算法中有最朴实的乘法运算思想，请各位细细体味。#include int main() int n; /阶乘大小 printf(请输入n的大小:); scanf(%d,&n); /从键盘接收阶乘大小 int a200; /确保保存最终运算结果的数组足够大 int carry; /进位 int digit = 1; /位数 a0 = 1; /将结果先初始化为1 int temp; /阶乘的任一元素与临时结果的某位的乘积结果