目前实现了，加，减，乘，乘方，阶乘和计算菲数，速度没有大幅度提高，唉，也没那么多时间做了，先放一放。（除法做得不好，太慢了，慢到不能用）

最后一次提升的快一些，因为我想到两个实数序列可以合并在一起，做为一个复数的实部和虚部，这样一起做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.028163
10k!    0.856568
20k!    2.215239
40k!    6.278020
80k!    16.574058
Test Date\2007\04\11

Factorial Function Test (1.01) [增加快速地址变换]
_______________________
n!      Cost Time (s)   Approximations
1000    0.025191        4.023872600770937735437 E 2567
10000   0.735035        2.846259680917054518906 E 35659
20000   1.960328        1.819206320230345134827 E 77337
40000   5.820808        2.091692422212132363320 E 166713
80000   15.231613       3.09772225166224928639 E 357506
Test Date\2007\04\12

Factorial Function Test (1.02) [时频结合免去地址变换]
_______________________
n!      Cost Time (s)   Approximations
1000    0.024248        4.023872600770937735437 E 2567
10000   0.724076        2.846259680917054518906 E 35659
20000   1.910845        1.819206320230345134827 E 77337
40000   5.747496        2.091692422212132363320 E 166713
80000   15.012617       3.09772225166224928639 E 357506

Factorial Function Test (1.03) [代码简单优化]
_______________________
n!      Cost Time (s)   Approximations
1000    0.033531        4.023872600770937735437 E 2567
10000   0.726679        2.846259680917054518906 E 35659
20000   1.770394        1.819206320230345134827 E 77337
40000   5.233378        2.091692422212132363320 E 166713
80000   13.751869       3.09772225166224928639 E 357506

Factorial Function Test (1.03)
_______________________
n!      Cost Time (s)   Approximations
1000    0.044938        4.023872600770937735437 E 2567
10000   0.683504        2.846259680917054518906 E 35659
20000   1.796226        1.819206320230345134827 E 77337
40000   5.204204        2.091692422212132363320 E 166713
80000   14.106093       3.09772225166224928639 E 357506

Factorial Function Test (1.04) [结合硬乘法]
_______________________
n!      Cost Time (s)   Approximations
1000    0.020884        4.023872600770937735437 E 2567
10000   0.699821        2.846259680917054518906 E 35659
20000   1.811458        1.819206320230345134827 E 77337
40000   5.331708        2.091692422212132363320 E 166713
80000   14.116834       3.09772225166224928639 E 357506

Factorial Function Test (1.05) [实数FFT]
_______________________
n!      Cost Time (s)   Approximations
1000    0.027728        4.023872600770937735437 E 2567
10000   0.594507        2.846259680917054518906 E 35659
20000   1.434080        1.819206320230345134827 E 77337
40000   4.070405        2.091692422212132363320 E 166713
80000   10.732933       3.09772225166224928639 E 357506

另外还有算菲数的：

Fibonacci Function Test (1.05)
_______________________
f(n)    Cost Time (s)   Approximations
1000    0.002684        4.34665576869374564356 E 208
10000   0.053351        3.364476487643178326662 E 2089
20000   0.088223        2.531162323732361242240 E 4179
40000   0.217730        1.432600165457807343833 E 8359
80000   0.500366        4.58917898454169424284 E 16718

在网上搜到一些牛人做的，还有功能很完善的HugeCalc，那些速度实在是快，比不得。等以后有时间了，再慢慢玩吧。

截图：

下载包：

http://upload.programfan.com/upfile/200704141621349.rar

只有两个文件：一个hugeint.h一个hugeint.cpp，开源。

评论