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

%%%

2020-04-16 21:50:08
回复

837951602

鸭上结果 https://duck.ac/submission/12556 https://duck.ac/submission/12557

2020-04-19 08:47:34
回复

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$ ，我写过一个粗糙的版本跑的很慢。。。

2020-05-17 18:22:34
回复

hly1204

抱歉，上面公式有错误， $X^F$ 是 $x$ dft后的序列， $x$ 的实部和虚部分别是两个实序列 $x_1,x_2$ 。

2020-05-17 18:24:45
回复

发表评论

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