【学习笔记】快速傅里叶变换

Posted on

12/20/2018 重写。

基本概念

多项式

系数表示

\begin{aligned} A(x)=& \sum_{i=1}^{n-1}a_ix^i \\ =& a_0+a_1x+a_2x^2\cdots+a_{n-1}x^{n-1}\end{aligned}

点值表示

\begin{aligned} y_i=& A(x_i) \\ =&\sum_{j=1}^{n-1}a_j x_i^j\end{aligned}

多项式乘法

$$C(x)=A(x)\times B(x) = \sum_{k=0}^{2n-2}(\sum_{k=i+j}a_i b_j)x^k$$

$$C_{y_i}=(\sum_{j=0}^{2n-1}a_j x_i^j)\times(\sum_{j=0}^{2n-1}b_j x_i^j)=A_{y_i}\times B_{y_i}$$

复数

单位根

$$\omega_n^k = \cos k \dfrac{2\pi}{n}+i \sin k \dfrac{2\pi}{n}$$

性质

\begin{aligned} \omega_{2n}^{2k}=&\omega_n^k \\ \omega_n^{k+\frac{n}{2}}=& -\omega_n^k \end{aligned}

欧拉公式

$$e^{ix}=\cos x+i\sin x$$

快速傅里叶变换 (Fast Fourier Transform)

$$A(x)=(a_0 + a_2 x^2 + a_4 x^4 + \cdots) + (a_1 x + a_3 x^3 + a_5 x^5 + \cdots)$$

\begin{aligned}A_1(x)=&a_0+a_2x+a_4x^2+\cdots \\ A_2(x)=& a_1 + a_3 x + a_5 x^2 + \cdots \end{aligned}

$$A(x)=A_1(x^2)+x A_2(x^2)$$

\begin{aligned} A(\omega_n ^ k) &= A_1(\omega_n ^ {2k}) + \omega_n ^ {k} A_2(\omega_n ^ {2k}) \\ &= A_1(\omega_{\frac{n}{2}} ^ {k}) + \omega_n ^ {k} A_2(\omega_{\frac{n}{2}} ^ {k}) \ \end{aligned}

\begin{aligned} A(\omega_n ^ {k + \frac{n}{2}}) &= A_1(\omega_n ^ {2k + n}) + \omega_n ^ {k + \frac{n}{2}} A_2(\omega_n ^ {2k + n}) \\ &= A_1(\omega_n ^ {2k} \times \omega_n ^ n)-\omega_n ^ {k} A_2(\omega_n ^ {2k} \times \omega_n ^ n) \\ &= A_1(\omega_n ^ {2k})-\omega_n ^ {k} A_2(\omega_n ^ {2k}) \\ &= A_1(\omega_{\frac{n}{2}} ^ {k})-\omega_n ^ {k} A_2(\omega_{\frac{n}{2}} ^ {k}) \ \end{aligned}

傅里叶逆变换 (Inverse Fourier Transform)

$$c_k = \sum\limits_{i = 0} ^ {n – 1} y_i (\omega_n ^ {-k}) ^ i$$

\begin{aligned} c_k &= \sum\limits_{i = 0} ^ {n – 1} y_i (\omega_n ^ {-k}) ^ i \\ &= \sum\limits_{i = 0} ^ {n – 1} (\sum\limits_{j = 0} ^ {n – 1} a_j (\omega_n ^ i) ^ j) (\omega_n ^ {-k}) ^ i \\ &= \sum\limits_{i = 0} ^ {n – 1} (\sum\limits_{j = 0} ^ {n – 1} a_j (\omega_n ^ j) ^ i) (\omega_n ^ {-k}) ^ i \\ &= \sum\limits_{i = 0} ^ {n – 1} (\sum\limits_{j = 0} ^ {n – 1} a_j (\omega_n ^ j) ^ i (\omega_n ^ {-k}) ^ i) \\ &= \sum\limits_{i = 0} ^ {n – 1} \sum\limits_{j = 0} ^ {n – 1} a_j (\omega_n ^ {j – k}) ^ i \\ &= \sum\limits_{j = 0} ^ {n – 1} a_j (\sum\limits_{i = 0} ^ {n – 1} (\omega_n ^ {j – k}) ^ i) \end{aligned}

\begin{aligned} c_i &= n a_i \\ a_i &= \frac{1}{n} c_i \end{aligned}

代码实现

蝴蝶操作

\begin{aligned} b(k) & \leftarrow a(k) + \omega_n ^ k \times a(\frac{n}{2} + k) \\ b(\frac{n}{2} + k) & \leftarrow a(k)-\omega_n ^ k \times a(\frac{n}{2} + k) \ \end{aligned}

\begin{aligned} t & \leftarrow \omega_n ^ k \times a(\frac{n}{2} + k) \\ a(\frac{n}{2}+k) & \leftarrow a(k)-t \\ a(k) & \leftarrow a(k)+t \end{aligned}

代码

1. keywet06
Aug 13, 2019

资瓷

2. keywet06
Aug 13, 2019

I fuck xml every day.

3. Wentao Ying
Aug 13, 2019

I think you can talk about som xml language.
because FFT is TOO slow.

4. keywet06
Aug 13, 2019

有人冒充我啊

• keywet06
Aug 13, 2019

邮箱打错了QAQ

5. zhouhongkai
Aug 13, 2019

I love WSY

6. keywet06
Aug 07, 2019

I love xml

• zhouhongkai
Aug 13, 2019

wow

• zhouhongkai
Aug 13, 2019

I love WSY

7. oyyj603470138
Sep 11, 2018

您应该从群上调和分析（DFT）讲起。。

• xgzepto
Sep 11, 2018

所以我坑了