*************************************(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,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次求余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#definePI3.1415926535897932384626433832795#defineE2.7182818284590452353602874713527#defineTEN91000000000typedefunsigned__int64UINT64;typedefunsignedlongDWORD;intcalcResultLen(DWORDn){returnlog10(2*PI*(double)n)/2+n*log10((double)n/E)+2;}voidprintfResult(DWORD*buff,intbuffLen){DWORD*p=buff;while(*p==0)p++;printf("\nn!=\n");for(inti=0;ipEnd;p--){prod=(UINT64)(*p)*(UINT64)i+(UINT64)carry;*p=prod%TEN9;carry=prod/TEN9;}if(carry>0){*(pBeg-len)=carry;len++;}}}intmain(intargc,char*argv[]){DWORDn=1;printf("n=?");scanf("%d",&n);intbuffLen=(calcResultLen(n)+8)/9;DWORD*buff=newDWORD[buffLen];calcFac(buff,buffLen,n);printfResult(buff,buffLen);delete[]buff;return0;}**************************************(2)********************************...
