gracias 发表于 2012-2-16 09:44:46

<求解惑> 关于FFT做大数乘法

不好意思请教下大家关于FFT做大数乘法的疑问。我在网上看到说可以用FFT做大数乘法,可以把数看成一个多项式.例如要计算两个N位数A(x) * B(x), 可以先计算A(x),B(x)的傅立叶变化得到A(X),B(X)，再计算A(X)*B(X)的逆变换即得到A(x)B(x)的结果.
我的疑问是最初的计算是A(x) * B(x) 是N*N长度的计算,可是在计算A(x),B(x)的变换结果长度依然是N啊,那么在计算逆变换之前的A(X)*B()不依然是一个N*N的计算么?到底是在什么地方减少了计算?

gxqcn 发表于 2012-2-16 10:13:07

FFT 及 IFFT 中的蝶形运算复杂度是 O(nlogn)，远比 O(n^2) 低。

gracias 发表于 2012-2-16 11:28:40

可是我的理解是蝶形运算是用来计算A(x) --->A(X), 但是还要计算A(X) * B(X) ，再计算其逆变换.才能得到结果.在计算A(X) * B(X)的时候不是又回到了问题的最开始么?

gxqcn 发表于 2012-2-16 11:35:21

哦，是我说的有误。
A(X)*B(X) 是对应项相乘，复杂度仅 O(n)，避免了通常的 O(n*n) 的复杂度。

gracias 发表于 2012-2-16 12:21:09

哦,是对应项相乘啊!谢谢！

仙剑魔 发表于 2012-2-17 13:51:38

A(0..n-1)长度n
B(0..m-1)长度m
FFT计算的是循环卷积
而A*B是线性卷积
所以计算前先把A,B补0,使得长度变成n+m-1
得到A'(0..n+m-2),B'(0..n+m-2)
计算FFT
得到A''(0..n+m-2),B''(0..n+m-2)
然后计算向量相乘的C=A''*B''
得到C(0..n+m-2)
计算IFFT
得到C'(0..n+m-2)
最后处理进位...

G-Spider 发表于 2012-2-17 14:02:03

参考：
http://bbs.emath.ac.cn/thread-2706-1-2.html

mathematica 发表于 2012-9-3 14:21:48

不错！！！！！！！！！！！

mathematica 发表于 2012-9-3 14:22:06

其实我也想知道这个问题

mathematica 发表于 2013-4-10 14:08:16

6# 仙剑魔


超过168小时不能评分,不过我还是赞美你一下!
页: [1]
查看完整版本: <求解惑> 关于FFT做大数乘法