目前实现了，加，减，乘，乘方，阶乘和计算菲数，速度没有大幅度提高，唉，也没那么多时间做了，先放一放。（除法做得不好，太慢了，慢到不能用） 最后一次提升的快一些，因为我想到两个实数序列可以合并在一起，做为一个复数的实部和虚部，这样一起做FFT会快一些。推导很简单，公式是： x(t),y(t)为N点实序列，设X(t)=DFT[x(t)] , Y(t)=DFT[y(t)]，记w(t)=x(t)+iy(t)，W(t)=DFT[w(t)]，于是由DFT的线性性质，有W(t)=X(t)+iY(t)，但是不一定就是W(t)的实部和虚部，为了由W(t)得到X(t)和Y(t)，是计算X(t)=(W(t)+W*((N-t))N)/2和Y(t)=(W(t)-W*((N-t))N)/2i。 这样一来，做一次乘法就只需要2次fft。 我的机子比较慢，测了几组数据，结果是： Factorial Function Test (1.0)_______________________n!      cost time (s)1k!     0.02816310k!    0.85656820k!    2.21523940k!    6.27802080k!    16.574058Test Date\2007\04\11 Factorial Function Test (1.01) [增加快速地址变换]_______________________n!      Cost Time (s)   Approximations1000    0.025191        4.023872600770937735437 E 256710000   0.735035        2.846259680917054518906 E 3565920000   1.960328        1.819206320230345134827 E 7733740000   5.820808        2.091692422212132363320 E 16671380000   15.231613       3.09772225166224928639 E 357506Test Date\2007\04\12 Factorial Function Test (1.02) [时频结合免去地址变换]_______________________n!      Cost Time (s)   Approximations1000    0.024248        4.023872600770937735437 E 256710000   0.724076        2.846259680917054518906 E 3565920000   1.910845        1.819206320230345134827 E 7733740000   5.747496        2.091692422212132363320 E 16671380000   15.012617       3.09772225166224928639 E 357506 Factorial Function Test (1.03) [代码简单优化]_______________________n!      Cost Time (s)   Approximations1000    0.033531        4.023872600770937735437 E 256710000   0.726679        2.846259680917054518906 E 3565920000   1.770394        1.819206320230345134827 E 7733740000   5.233378        2.091692422212132363320 E 16671380000   13.751869       3.09772225166224928639 E 357506 Factorial Function Test (1.03)_______________________n!      Cost Time (s)   Approximations1000    0.044938        4.023872600770937735437 E 256710000   0.683504        2.846259680917054518906 E 3565920000   1.796226        1.819206320230345134827 E 7733740000   5.204204        2.091692422212132363320 E 16671380000   14.106093       3.09772225166224928639 E 357506 Factorial Function Test (1.04) [结合硬乘法]_______________________n!      Cost Time (s)   Approximations1000    0.020884        4.023872600770937735437 E 256710000   0.699821        2.846259680917054518906 E 3565920000   1.811458        1.819206320230345134827 E 7733740000   5.331708        2.091692422212132363320 E 16671380000   14.116834       3.09772225166224928639 E 357506 Factorial Function Test (1.05) [实数FFT]_______________________n!      Cost Time (s)   Approximations1000    0.027728        4.023872600770937735437 E 256710000   0.594507        2.846259680917054518906 E 3565920000   1.434080        1.819206320230345134827 E 7733740000   4.070405        2.091692422212132363320 E 16671380000   10.732933       3.09772225166224928639 E 357506 另外还有算菲数的： Fibonacci Function Test (1.05)_______________________f(n)    Cost Time (s)   Approximations1000    0.002684        4.34665576869374564356 E 20810000   0.053351        3.364476487643178326662 E 208920000   0.088223        2.531162323732361242240 E 417940000   0.217730        1.432600165457807343833 E 835980000   0.500366        4.58917898454169424284 E 16718 在网上搜到一些牛人做的，还有功能很完善的HugeCalc，那些速度实在是快，比不得。等以后有时间了，再慢慢玩吧。 截图： 下载包： http://upload.programfan.com/upfile/200704141621349.rar 只有两个文件：一个hugeint.h一个hugeint.cpp，开源。

评论