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长度不足。