UOJ Logo 837951602的博客

博客

FFT利用复数减少一半点

2020-04-16 12:52:04 By 837951602

我看#34的榜,double做法都是 $$x_i=a_{2i}+ia_{2i+1}\\Z_i=X_iY_i-\frac 14\left(1+w_N^i\right)\left(X_i-\overline{X_{N-i}}\right)\left(Y_i-\overline{Y_{N-i}}\right)$$ 而不是 $$x_i=a_iu^i+a_{i+n}u^{i+n}\\Z_i=X_iY_i$$ 这两个方法,哪个更显然?哪个效率高?(我提交改了输出挂还去了swap过程,但另一种方法也能做)

评论

laosb
%%%
837951602
鸭上结果 https://duck.ac/submission/12556 https://duck.ac/submission/12557
hly1204
楼主有兴趣的话试试用一次fft处理两个实序列的dft和这两个比哪个快呢 $$X_1^F(k)=\frac{1}{2}[X^F(k)+X^{F*}(N-k)]$$ $$X_2^F(k)=\frac{\mathrm{j}}{2}[X^{F*}(N-k)-X^F(k)]$$ $X^F$ 的实部是 $x_1$ ,虚部是 $x_2$ ,我写过一个粗糙的版本跑的很慢。。。
hly1204
抱歉,上面公式有错误, $X^F$ 是 $x$ dft后的序列, $x$ 的实部和虚部分别是两个实序列 $x_1,x_2$ 。

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。