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

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

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

不好意思请教下大家关于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小时不能评分,不过我还是赞美你一下!

账号		自动登录	找回密码
密码			欢迎注册

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

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。