FFT与离散卷积与大数乘法
最近由于专业的原因,不得不需要计算离散卷积,居然发现使用快速傅里叶变换FFT,可以很快地加速卷积的运算,同时我又想到计算大数的乘法,其实也就是卷积呀,
真没想到FFT还能在整数的乘法和离散卷积上有用武之地!
如果不使用FFT的话,计算卷积将是很慢的事情,但是使用了FFT后,发现计算结果块了
很多,真的是有所感叹 虽然我不知道怎么计算FFT，但早已知道大数的乘法是采用FFT或FNT的 现在FFT乘法基本流程还是和浮点FFT一样的
所以要求模是$2^n -+ 1$ 还以为是详细分析和推导 一直被考试困扰......烦:M: 。
前些日子借了有关这方面的书，还没看完，等忙完了再继续，又回到了数学分析的年代，呵呵...
《快速傅里叶变换及其c程序》中国科学版
《Fourier 分析》清华版
------------------------------------------------
记得某开源计算pi时构建大数乘用了FFT，日本的吧，(gmp就不提了) 我在2006年学习过FFT，并写了几个FFT程序，详见 征集FFT算法的代码和算法
其后在csdn下载中心给出了所有的7种FFT算法的源代码和测试代码，可从 7种FFT代码和测试程序 CSDN 下载频道 下载 当然不是说用了FFT，大数乘法就快了，要依赖于具体平台且要达到一定的数值规模
//=============================
//大数乘法C=A*B FFT卷积
//C=A*B (N=16)
A=0000000000113212(mod 10)
B=0000000000311312(mod 10)
C=0000034 11 13 12 21 14 13 1144(mod 10) C为A，B的卷积
=0000035244254144
//=>修改基100如下(N=8)：
//=============================
A=0 0 0 0 0 11 32 12(mod 100)
B=0 0 0 0 0 31 13 12(mod 100)
C=0 0 0 341 1135920540144(mod 100)
=0 0 352 44 25 41 44
//=>修改基1000如下(N=4)：
//=============================
A=0 0 113 212(mod 1000)
B=0 0 311 312(mod 1000)
C=035143 101188 66144(mod 1000)
=35 244 254 144
//=>修改基10000如下(N=4)：
//=============================
A=0 0 11 3212(mod 10000)
B=0 0 31 1312(mod 10000)
C=0341 114004 4214144(mod 10000)
=0352 4425 4144
===============================
===============================
//A=00003212
//B=00001312
//C=03 11 10 13 1144 (mod 10)
//C=04214144
// =============================
//A=00003212
//B=00000312
//C=0099 11 1144 (mod 10)
//C=01002144
// ============================
//A=00003212
//B=00011312
//C=35 12 12 13 1144 (mod 10)
//C=36334144
//=============================
//C=A*B
//A=00113212(mod 10)
//B=00311312(mod 10)
//出错 上面最后一个举例“出错”的原因估计是：结果有11位，而你用的FFT长度不足。
页:
[1]