FFT与离散卷积与大数乘法

mathematica

最近由于专业的原因,不得不需要计算离散卷积,居然发现使用快速傅里叶变换FFT, 可以很快地加速卷积的运算,同时我又想到计算大数的乘法,其实也就是卷积呀, 真没想到FFT还能在整数的乘法和离散卷积上有用武之地! 如果不使用FFT的话,计算卷积将是很慢的事情,但是使用了FFT后,发现计算结果块了 很多,真的是有所感叹

qianyb

虽然我不知道怎么计算FFT，但早已知道大数的乘法是采用FFT或FNT的

无心人

现在FFT乘法基本流程还是和浮点FFT一样的 所以要求模是$2^n -+ 1$

showjim

还以为是详细分析和推导

G-Spider

一直被考试困扰......烦 。 前些日子借了有关这方面的书，还没看完，等忙完了再继续，又回到了数学分析的年代，呵呵... 《快速傅里叶变换及其c程序》中国科学版 《Fourier 分析》清华版 ------------------------------------------------ 记得某开源计算pi时构建大数乘用了FFT，日本的吧，(gmp就不提了)

liangbch

我在2006年学习过FFT，并写了几个FFT程序，详见 征集FFT算法的代码和算法 其后在csdn下载中心给出了所有的7种FFT算法的源代码和测试代码，可从 7种FFT代码和测试程序 CSDN 下载频道 下载

G-Spider

当然不是说用了FFT，大数乘法就快了，要依赖于具体平台且要达到一定的数值规模 //============================= //大数乘法C=A*B FFT卷积 //C=A*B (N=16) A=0 0 0 0 0 0 0 0 0 0 1 1 3 2 1 2 (mod 10) B=0 0 0 0 0 0 0 0 0 0 3 1 1 3 1 2 (mod 10) C=0 0 0 0 0 3 4 11 13 12 21 14 13 11 4 4 (mod 10) C为A，B的卷积 =0 0 0 0 0 3 5 2 4 4 2 5 4 1 4 4 //=>修改基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 1135 920 540 144 (mod 100) =0 0 3 52 44 25 41 44 //=>修改基1000如下(N=4)： //============================= A=0 0 113 212 (mod 1000) B=0 0 311 312 (mod 1000) C=0 35143 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=0 341 114004 4214144 (mod 10000) =0 352 4425 4144 =============================== =============================== //A=0 0 0 0 3 2 1 2 //B=0 0 0 0 1 3 1 2 //C=0 3 11 10 13 11 4 4 (mod 10) //C=0 4 2 1 4 1 4 4 // ============================= //A=0 0 0 0 3 2 1 2 //B=0 0 0 0 0 3 1 2 //C=0 0 9 9 11 11 4 4 (mod 10) //C=0 1 0 0 2 1 4 4 // ============================ //A=0 0 0 0 3 2 1 2 //B=0 0 0 1 1 3 1 2 //C=3 5 12 12 13 11 4 4 (mod 10) //C=3 6 3 3 4 1 4 4 //============================= //C=A*B //A=0 0 1 1 3 2 1 2 (mod 10) //B=0 0 3 1 1 3 1 2 (mod 10) //出错

gxqcn

上面最后一个举例“出错”的原因估计是：结果有11位，而你用的FFT长度不足。