欢迎来到天天文库
浏览记录
ID:59173975
大小:18.50 KB
页数:9页
时间:2020-10-30
《大数阶乘算法.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!=");
此文档下载收益归作者所有