고속 푸리에 변환 (Fast Fourier Transform, FFT) 은 이산 푸리에 변환 을 빠르게 계산하는 방법입니다.
이산 푸리에 변환 (Discrete Fourier Transform, DFT)합 $\sum\limits_{k = 0}^{T - 1} a_{k} e^{i \frac{- 2 \pi k n}{T}}$ 을 조금은 다른 관점에서 볼 수 있습니다.
주기가 $T$인 복소수열 $\{a_{n}\}$을 DFT 한 복소수열 $\{A_{n}\}$ $$ A_{n} = \sum_{k = 0}^{T - 1} a_{k} e^{i \frac{- 2 \pi k n}{T}} = \sum_{k = 0}^{T - 1} a_{k} \left\{ \cos\left( \frac{2 \pi k n}{T} \right) - i \sin\left( \frac{2 \pi k n}{T} \right) \right\} $$
이산 푸리에 역변환 (Inverse Discrete Fourier Transform, IDFT)
복소수열 $\{A_{n}\}$을 다시 $\{a_{n}\}$으로 변환시키기 위한 IDFT 과정 $$ a_{n} = \frac{1}{T} \sum_{k = 0}^{T - 1} A_{k} e^{i \frac{2 \pi k n}{T}} = \frac{1}{T} \sum_{k = 0}^{T - 1} A_{k} \left\{ \cos\left( \frac{2 \pi k n}{T} \right) + i \sin\left( \frac{2 \pi k n}{T} \right) \right\} $$
a[1::2]라고 쓸 수 있고, 마찬가지로 $f_{a\_even}(x)$의 계수는 a[0::2] ( == a[::2] ) 입니다. w = complex(math.cos(math.pi * 2 / T), -math.sin(math.pi * 2 / T)) 는 $w = e^{i \frac{- 2 \pi}{T}} = \cos\left( \frac{2 \pi}{T} \right) - i \sin\left( \frac{2 \pi}{T} \right)$ 과 동일합니다. i < T_half 이고, T가 2의 거듭제곱꼴이므로 T_half도 2의 거듭제곱꼴이므로, or 연산자 | 를 써서 "i | T_half == i + T_half" 라고 할 수 있습니다. (덧셈 연산자보다 비트 연산자가 더 빠릅니다.) (even[i] + (w ** i) * odd[i]) / 2 같이 2로 나눠주는 과정을 $\lg T$번 (재귀 횟수가 $\lg T$) 하므로 $2^{\lg T} = T$에서 총 T만큼 나눠짐을 알 수 있습니다. (이런 계산이 싫다면 2 나눔 없이 IFFT 계산 후 함수 밖에서 일일이 T로 나눠주는 방법이 있겠습니다.)
조금 더 빠른 FFT를 해봅시다.
ex) 길이가 $2^5$이면 $a_{11} = a_{01101} = a_{b_{4}b_{3}b_{2}b_{1}b_{0}}$에서 $b_{4} = 0, b_{3} = 1, b_{2} = 1, b_{1} = 0, b_{0} = 1$
$\mathcal{L}_{n} = [p_n, q_n)$에서 $\mathcal{L}_{n + 1} = [p_n + \frac{q_n - p_n}{2}, q_n)$ 이거나 $\mathcal{L}_{n + 1} = [p_n, q_n - \frac{q_n - p_n}{2})$이고, 어떤 경우에도 $r_{n + 1} = \frac{q_n - p_n}{2}$이므로, $r_n$의 정의에서 $r_{n + 1} = \frac{r_n}{2}$이다. 따라서 $r_{n} = \frac{r_0}{2^n}$임을 알 수 있다.
$a_{k}$가 $\underset{L - 1}{\alpha}$ 에서 있을 구간은 $\mathcal{L}_{L - 1} = [p_{L - 1}, q_{L - 1})$인데, 보조정리 1에서 $q_{L - 1} - p_{L - 1} = 1$이다. 따라서 $p_{L - 1} + 1 = q_{L - 1}$이다.
만약 $a_{k}$가 구간 $\mathcal{L}_{n}$에서 짝수 번째라면 $\mathcal{L}_{n + 1}$에서 $\mathcal{L}_{n + 1} = [p_n + \frac{r_n}{2}, q_n)$이고, 홀수 번째라면 $\mathcal{L}_{n + 1} = [p_n, q_n - \frac{r_n}{2})$이다.
보조정리 3에서 $p_{L - 1} = \sum\limits_{n = 0}^{L - 1} b_{n} \times 2^{L - n - 1}$ 이다.
보조정리 2에서 $0 \leq k < T$인 모든 정수 $k$에 대해서 $\underset{L - 1}{\alpha}$ 에서 $a_{k}$의 위치는 $p_{L - 1}$이다.
재귀는 기본적으로 느리다는 것이 알려져있으므로, 재귀를 쓰지 않는 법을 찾아봅니다.
예를 들어, 우리는 길이가 $16$인 리스트 $a = [a_0, a_1, \cdots, a_{14}, a_{15}]$를 FFT한 결과인 $A = [A_0, A_1, \cdots, A_{14}, A_{15}]$를 얻고 싶습니다.
위의 재귀 방법에서는 $FFT([a_0, a_2, a_4, a_6, a_8, a_{10}, a_{12}, a_{14}]), FFT([a_1, a_3, a_5, a_7, a_9, a_{11}, a_{13}, a_{15}])$를 구해야 합니다. (앞으로 $FFT(list)$를 $\mathcal{F}(list)$ 라고 표현하겠습니다.)
그런데 애초에 그냥
$$
\underset{0}{\alpha} = [\mathcal{F}([a_0, a_2, a_4, a_6, a_8, a_{10}, a_{12}, a_{14}]), \mathcal{F}([a_1, a_3, a_5, a_7, a_9, a_{11}, a_{13}, a_{15}])]
$$
라는 리스트가 있었다면 어땠을까요?
$0 \leq k < 8$인 모든 정수 $k$에 대해
$$
\begin{align}
A[k] & = \underset{0}{\alpha}[k] + e^{i \frac{-2 \pi k}{16}} \underset{0}{\alpha}[k + 8] \\
A[k + 8] & = \underset{0}{\alpha}[k] - e^{i \frac{-2 \pi k}{16}} \underset{0}{\alpha}[k + 8]
\end{align}
$$
로 간단하게 구할 수 있었을 겁니다.
$\underset{0}{\alpha}$ 리스트를 간단히 구하려면 어떤 리스트가 있어야 할까요?
$$
\underset{1}{\alpha} = [\mathcal{F}([a_0, a_4, a_8, a_{12}]), \mathcal{F}([a_2, a_6, a_{10}, a_{14}]), \mathcal{F}([a_1, a_5, a_9, a_{13}]), \mathcal{F}([a_3, a_7, a_{11}, a_{15}])]
$$
라는 리스트가 있었더라면 모든 $j = 0, 8$과 $0 \leq k < 4$인 정수 $k$에 대하여
$$
\begin{align}
\underset{0}{\alpha}[j + k] & = \underset{1}{\alpha}[j + k] + e^{i \frac{-2 \pi k}{8}} \underset{1}{\alpha}[j + k + 4] \\
\underset{0}{\alpha}[j + k + 4] & = \underset{1}{\alpha}[j + k] - e^{i \frac{-2 \pi k}{8}} \underset{1}{\alpha}[j + k + 4]
\end{align}
$$
로 계산할 수 있었을 것입니다.
이제 감이 오셨을 겁니다. $\underset{1}{\alpha}$를 구하려면
$$
\underset{2}{\alpha} = [\mathcal{F}([a_0, a_8]), \mathcal{F}([a_4, a_{12}]), \mathcal{F}([a_2, a_{10}]), \mathcal{F}([a_6, a_{14}]), \mathcal{F}([a_1, a_9]), \mathcal{F}([a_5, a_{13}]), \mathcal{F}([a_3, a_{11}]), \mathcal{F}([a_7, a_{15}])]
$$
이 필요했을 겁니다. 계산식은 모든 $j = 0, 4, 8, 12$와 $0 \leq k < 2$인 정수 $k$에 대하여
$$
\begin{align}
\underset{1}{\alpha}[j + k] & = \underset{2}{\alpha}[j + k] + e^{i \frac{-2 \pi k}{4}} \underset{2}{\alpha}[j + k + 2] \\
\underset{1}{\alpha}[j + k + 2] & = \underset{2}{\alpha}[j + k] - e^{i \frac{-2 \pi k}{4}} \underset{2}{\alpha}[j + k + 2]
\end{align}
$$
로 계산할 수 있었을 것입니다.
$\underset{2}{\alpha}$를 구하려면
$$
\underset{3}{\alpha} = [\mathcal{F}([a_0]), \mathcal{F}([a_8]), \mathcal{F}([a_4]), ... \mathcal{F}([a_{15}])]
$$
가 필요한데, FFT의 정의에서 길이가 1인 리스트 [x]의 FFT 결과는 $\mathcal{F}([x]) = x$임을 알 수 있으니,
$$
\underset{3}{\alpha} = [a_0, a_8, a_4, a_{12}, a_2, a_{10}, a_6, a_{14}, a_1, a_9, a_5, a_{13}, a_3, a_{11}, a_7, a_{15}]
$$
임을 알 수 있습니다.
필요한 리스트를 보자면
$$
\begin{align}
A & = [A_0, A_1, A_2, A_3, A_4, A_5, A_6, A_7, A_8, A_9, A_{10}, A_{11}, A_{12}, A_{13}, A_{14}, A_{15}] \\
& \Uparrow \\
\underset{0}{\alpha} & = [\mathcal{F}([a_0, a_2, a_4, a_6, a_8, a_{10}, a_{12}, a_{14}]), \mathcal{F}([a_1, a_3, a_5, a_7, a_9, a_{11}, a_{13}, a_{15}])] \\
& \Uparrow \\
\underset{1}{\alpha} & = [\mathcal{F}([a_0, a_4, a_8, a_{12}]), \mathcal{F}([a_2, a_6, a_{10}, a_{14}]), \mathcal{F}([a_1, a_5, a_9, a_{13}]), \mathcal{F}([a_3, a_7, a_{11}, a_{15}])] \\
& \Uparrow \\
\underset{2}{\alpha} & = [\mathcal{F}([a_0, a_8]), \mathcal{F}([a_4, a_{12}]), \mathcal{F}([a_2, a_{10}]), \mathcal{F}([a_6, a_{14}]), \mathcal{F}([a_1, a_9]), \mathcal{F}([a_5, a_{13}]), \mathcal{F}([a_3, a_{11}]), \mathcal{F}([a_7, a_{15}])] \\
& \Uparrow \\
\underset{3}{\alpha} & = [a_0, a_8, a_4, a_{12}, a_2, a_{10}, a_6, a_{14}, a_1, a_9, a_5, a_{13}, a_3, a_{11}, a_7, a_{15}]
\end{align}
$$
입니다. 즉, 어떻게든 $\underset{3}{\alpha}$ 리스트를 만들어낸다면 되는 것입니다.
리스트 $a$만을 가지고, $\underset{3}{\alpha}$라는 리스트를 어떻게 만들 수 있을까요?
$\underset{3}{\alpha}$ 내의 수열의 인덱스를 전부 4자리수의 2진법으로 표기해보겠습니다.
$$
\underset{3}{\alpha} = [a_{0000}, a_{1000}, a_{0100}, a_{1100}, a_{0010}, a_{1010}, a_{0110}, a_{1110}, a_{0001}, a_{1001}, a_{0101}, a_{1101}, a_{0011}, a_{1011}, a_{0111}, a_{1111}]
$$
이제 $\lambda$라는 수열을 정의해보겠습니다. $\underset{3}{\alpha}$의 $i$번째 원소의 2진법 인덱스를 뒤집은 것을 $i_{rev}$라 할 때, $\lambda[i] = a_{i_{rev}}$ 입니다.
예를 들어, $i = 3$이면 $\underset{3}{\alpha}[3] = a_{1100}$이고, $i_{rev}$는 $1100$을 뒤집은 $0011$이므로, $\lambda[3] = a_{0011}$입니다.
이제 $\lambda$를 일일이 적어본다면...
$$
\lambda = [a_{0000}, a_{0001}, a_{0010}, a_{0011}, a_{0100}, a_{0101}, a_{0110}, a_{0111}, a_{1000}, a_{1001}, a_{1010}, a_{1011}, a_{1100}, a_{1101}, a_{1110}, a_{1111}]
$$
2진법 표기를 다시 10진법으로 바꿔보겠습니다.
$$
\lambda = [a_{0}, a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, a_{6}, a_{7}, a_{8}, a_{9}, a_{10}, a_{11}, a_{12}, a_{13}, a_{14}, a_{15}]
$$
!!!
$\lambda$는 $a$와 완전히 동일합니다.
어째서 이런 일이 생길까요?
Bit Reversal 과정 증명
Bit Reversal 과정 예시
$b_{0} = 1$이므로, 구간 $[0, 2^5)$에서 홀수번째 이므로 odd 리스트 (즉, 오른쪽) 으로 이동하게 될 것이므로 $\underset{0}{\alpha}$에서는 $[2^4, 2^5)$로 이동하게 된다.
즉, $\beta$에서의 인덱스도 $\beta[1\times\times\times\times]$이 될 것이다.
($[2^4, 2^5)$ 구간에 있으므로 2진법에서 $2^4$의 자리수는 무조건 $1$이 된다.)
$b_{1} = 0$이므로, 구간 $[2^4, 2^5)$에서 짝수번째 이므로 even 리스트로 (즉, 왼쪽) 으로 이동하게 될 것이므로, $\underset{1}{\alpha}$에서는 $[2^4, 2^5 - 2^3) = [2^4, 2^4 + 2^3)$로 이동하게 된다.
즉, $\beta$에서의 인덱스도 $\beta[1 0 \times\times\times]$이 될 것이다.
($[2^4, 2^4 + 2^3)$ 구간에 있으므로 2진법에서 $2^3$의 자리수는 무조건 $0$이 된다.)
$b_{2} = 1$이므로, 구간 $[2^4, 2^4 + 2^3)$에서 홀수번째 이므로 odd 리스트로 (즉, 오른쪽) 으로 이동하게 될 것이므로, $\underset{2}{\alpha}$에서는 $[2^4 + 2^2, 2^5 - 2^3) = [2^4 + 2^2, 2^4 + 2^3)$로 이동하게 된다.
즉, $\beta$에서의 인덱스도 $\beta[1 0 1\times\times]$이 될 것이다.
($[2^4 + 2^2, 2^4 + 2^3)$ 구간에 있으므로 2진법에서 $2^2$의 자리수는 무조건 $1$이 된다.)
$b_{3} = 1$이므로, 구간 $[2^4 + 2^2, 2^4 + 2^3)$에서 홀수번째 이므로 odd 리스트로 (즉, 오른쪽) 으로 이동하게 될 것이므로, $\underset{3}{\alpha}$에서는 $[2^4 + 2^2 + 2^1, 2^5 - 2^3) = [2^4 + 2^2 + 2^1, 2^4 + 2^3)$로 이동하게 된다.
즉, $\beta$에서의 인덱스도 $\beta[1 0 1 1\times]$이 될 것이다.
($[2^4 + 2^2 + 2^1, 2^4 + 2^3)$ 구간에 있으므로 2진법에서 $2^1$의 자리수는 무조건 $1$이 된다.)
$b_{4} = 0$이므로, 구간 $[2^4 + 2^2 + 2^1, 2^4 + 2^3)$에서 짝수번째 이므로 even 리스트로 (즉, 왼쪽) 으로 이동하게 될 것이므로, $\underset{4}{\alpha}$에서는 $[2^4 + 2^2 + 2^1, 2^5 - 2^3 - 2^0) = [2^4 + 2^2 + 2^1, 2^4 + 2^2 + 2^1 + 2^0)$로 이동하게 된다.
즉, $\beta$에서의 인덱스도 $\beta[1 0 1 1 0]$이 될 것이다.
($[2^4 + 2^2 + 2^1, 2^4 + 2^2 + 2^1 + 2^0)$ 구간에 있으므로 2진법에서 $2^0$의 자리수는 무조건 $0$이 된다.)
$L$은 $L = \lg T$이다.
$[p, q)$는 반닫힌 구간 표기이다. ("$c$가 구간 $[p, q)$에 있다" == $p \leq c < q$)
$0 \leq k < T$인 모든 정수 $k$에 대하여 $a$의 $k$번째 값은 $a[k]$, $a_{k}$ 두 가지로 표기하고 두 가지는 동일하다.
인덱스인 $k$의 이진 길이 $L$로 나타낸 것을 $b_{L - 1}, b_{L - 2}, \cdots , b_{1}, b_{0}$ 로 표기 (즉, $b_{n}$은 $k$의 $n$번째 비트, $k = b_{L - 1}b_{L - 2}\cdots b_{1}b_{0} = \sum\limits_{n = 0}^{L - 1} b_{n} 2^{n}$)
$k_{rev}$를 $k_{rev} = b_{0}b_{1}\cdots b_{L - 2}b_{L - 1} = \sum\limits_{n = 0}^{L - 1} b_{L - 1 - n} 2^{n}$라고 함
$\beta$는 $\beta[k_{rev}] = a_{k}$ 인 리스트
임의의 리스트 $\mathcal{A}_{k} = [t_{0}, t_{1}, t_{2}, t_{3}, \cdots]$ 에 대하여 ${\mathcal{A}_{k}}_{even} = [t_{0}, t_{2}, t_{4}, \cdots]$, ${\mathcal{A}_{k}}_{odd} = [t_{1}, t_{3}, t_{5}, \cdots]$ 라고 정의한다.
$\underset{-1}{\alpha} = [\mathcal{F}(a)]$이라고 정의
$0 \leq n < L$인 정수 $n$에 대하여 $\underset{n - 1}{\alpha} = [\mathcal{F}(\mathcal{A}_{0}), \mathcal{F}(\mathcal{A}_{1}), \cdots , \mathcal{F}(\mathcal{A}_{2^{n}})]$이라 할 때, $\underset{n}{\alpha} = [\mathcal{F}({\mathcal{A}_{0}}_{even}), \mathcal{F}({\mathcal{A}_{0}}_{odd}), \mathcal{F}({\mathcal{A}_{1}}_{even}), \mathcal{F}({\mathcal{A}_{1}}_{odd}), \cdots , \mathcal{F}({\mathcal{A}_{2^{n}}}_{even}), \mathcal{F}({\mathcal{A}_{2^{n}}}_{odd})]$이라 한다.
이제 다음과 같은 정리를 증명하면 된다.
Bit Reversal 정리
표기법 1. "$a_{k} = \underset{n}{\alpha}[j]$" 라는 표기는 $a$의 $k$번째 원소가 $\underset{n}{\alpha}$을 풀어썼을 때 $j$번째라는 것을 뜻한다.
$\beta[k_{rev}] = a_{k}$ 인 리스트 $\beta$에 대하여, $$ \underset{L - 1}{\alpha} = \beta $$
ex) $L = 4$ 일 때, $\underset{2}{\alpha} = [\mathcal{F}([a_0, a_8]), \mathcal{F}([a_4, a_{12}]), \mathcal{F}([a_2, a_{10}]), \cdots]$ 에서 $a_{2} = \underset{2}{\alpha}[4]$, $a_{12} = \underset{2}{\alpha}[3]$ 이다.
표기법 2. $a_{k}$가 $\underset{n}{\alpha}$에서 존재할 수 있을 구간을 $\mathcal{L}_{n} = [p_n, q_n)$이라 한다. ($\mathcal{L}_{-1} = [0, 2^L) = [0, T)$)
표기법 3. $q_n - p_n = r_n$이라 하자.
만약 $a_{k}$가 구간 $\mathcal{L}_{n}$에서 짝수 번째라면 $\mathcal{L}_{n + 1}$에서도 even이 모인 부분 (즉, 더 작은 쪽)에 있을 것이므로, $\mathcal{L}_{n + 1} = [p_n, q_n - \frac{r_n}{2})$이고, 홀수 번째라면 $\mathcal{L}_{n + 1} = [p_n + \frac{r_n}{2}, q_n)$이다.
보조정리 1. $r_{L - 1} = 1$
보조정리 1 증명
$r_{0} = 2^{L - 1}$이므로, $r_{L - 1} = \frac{r_0}{2^{L - 1}} = \frac{2^{L - 1}}{2^{L - 1}} = 1$ 이다.
($0 \leq k< L$인 모든 정수 $k$에 대하여 $r_{k} = 2^{L - k - 1}$임도 알 수 있다.)
보조정리 2 증명
$a_k$가 $p_{L - 1} \leq x < q_{L - 1}$인 정수 $x$에 대하여 $\underset{L - 1}{\alpha}$에서 $x$번째에 있을 수 있는데, $p_{L - 1} \leq x < q_{L - 1}$ 에서 $p_{L - 1} \leq x < p_{L - 1} + 1$이고, 이를 만족시키는 정수 $x$는 $p_{L - 1}$밖에 없다.
보조정리 3 증명
$b_{n} = 0$이면 $\mathcal{L}_{n - 1}$에서 짝수번째이고, 따라서 $b_{n} = 0$이면 $p_{n - 1} = p_{n}$이고, $b_{n} = 1$ 이면 $p_{n - 1} + \frac{r_{n - 1}}{2} = p_{n - 1} + \frac{2^{L - n}}{2} = p_{n - 1} + 2^{L - n - 1} = p_{n}$
$p_{-1} = 0$ 이고 $\mathcal{P}_{n} = p_{n} - p_{n - 1}$이라 두면 $p_{k} = \sum\limits_{n = 0}^{k} \mathcal{P}_{n}$ 에서 $0 \leq n < L$인 모든 정수 $n$에 대해 $b_{n} = 1$이어야 $\mathcal{P}_{n} = 2^{L - n - 1}$이고, $b_{n} = 0$이면 $\mathcal{P}_{n} = 0$이므로, $\mathcal{P}_{n} = \left[b_{n} = 1\right] \times 2^{L - n - 1} = b_{n} \times 2^{L - n - 1}$이라 할 수 있다.
따라서 $p_{L - 1} = \sum\limits_{n = 0}^{L - 1} \left[b_{n} = 1\right] \times 2^{L - n - 1} = \sum\limits_{n = 0}^{L - 1} b_{n} \times 2^{L - n - 1}$ 이다. ($\left[ P \right]$는 아이버슨 괄호 )
보조정리 4 증명
$b_{0}b_{1} \cdots b_{L - 2}b_{L - 1} = \sum\limits_{n = 0}^{L - 1} b_{L - 1 - n} \times 2^{n}$
$N = L - 1 - n$으로 치환하면 $\sum\limits_{N = L - 1}^{0} b_{N} \times 2^{L - N - 1} = \sum\limits_{N = 0}^{L - 1} b_{N} \times 2^{L - N - 1}$
$\sum$에서 $N, n$은 더미변수 이므로 $N$을 $n$이라 써도 상관이 없으므로 $b_{0}b_{1} \cdots b_{L - 2}b_{L - 1} = \sum\limits_{n = 0}^{L - 1} b_{n} \times 2^{L - n - 1}$ 이고, 이는 $p_{L - 1}$과 같다.
Bit Reversal 정리
$\beta[k_{rev}] = a_{k}$ 인 리스트 $\beta$에 대하여, $$ \underset{L - 1}{\alpha} = \beta $$
Bit Reversal 정리 증명
보조정리 4에서 $p_{L - 1} = b_{0}b_{1} \cdots b_{L - 2}b_{L - 1} = k_{rev}$이다.
따라서 $0 \leq k < T$인 모든 정수 $k$에 대해서 $a_{k} = \underset{L - 1}{\alpha}[p_{L - 1}] = \underset{L - 1}{\alpha}[k_{rev}]$이다.
또, ${k_{rev}}_{rev} = k$이므로, $\underset{L - 1}{\alpha}[k] = a_{k_{rev}}$라고 할 수 있다.
표기법 1에서 $\underset{L - 1}{\alpha} = [\mathcal{F}([a_{0_{rev}}]), \mathcal{F}([a_{1_{rev}}]), \mathcal{F}([a_{2_{rev}}]), \cdots]$ 임을 알 수 있고, $\mathcal{F}([x]) = [x]$에서 $\underset{L - 1}{\alpha} = [[a_{0_{rev}}], [a_{1_{rev}}], [a_{2_{rev}}], \cdots]$ 임을 알 수 있다.
또, $\beta$의 정의 $\beta[k_{rev}] = a_{k}$에서 $\beta[k] = a_{k_{rev}}$이므로, $\underset{L - 1}{\alpha} = \beta$임을 알 수 있다.
사실 $\beta[k] = a_{k_{rev}}$이 아닌 $\beta[k] = [a_{k_{rev}}]$로 보는게 정확하지만, Bit Reversal을 거치고 $\beta[k] = a_{k_{rev}}$라고 정의한 리스트 $\beta$가 굉장히 유용한 성질을 가진다 라고 이해해주시면 감사하겠습니다.
+= $2^{L - 1 - n}$ 을 한다. a[k], a[K] = a[K], a[k] 로 바꾸면 안되고, $k < K$ (혹은 $k > K$)인 경우에만 a[k], a[K] = a[K], a[k] 으로 바꾸면 되겠습니다. a[p], a[q] 가 교체되고, $k = q$일 때 또 다시 a[p], a[q] 가 교체되어서 결국 원래대로 돌아와버립니다. k & (1 << n) 의 값이 $2^{n}$이면 $b_{n} = 1$이고, 값이 $0$이면 $b_{n} = 0$입니다. += $2^{L - 1 - n}$을 해줘도 좋지만, 마찬가지로 비트 연산자 or (|) 를 써서 K |= 1 << (L - 1 - n) 으로 해줄 수 있습니다. 주기가 $T$인 수열 $\{a_{n}\}$, $\{b_{n}\}$에 대하여 $A_{n} = \sum\limits_{k = 0}^{T - 1} a_{k} e^{i \frac{- 2 \pi k n}{T}}$, $B_{n} = \sum\limits_{k = 0}^{T - 1} b_{k} e^{i \frac{- 2 \pi k n}{T}}$ 이라 하자.증명은 이산 푸리에 변환의 합성곱 에서 볼 수 있습니다.
$$ c_{n} = \sum_{k = 0}^{T - 1} a_{k} b_{n - k} $$ 이면 $$ C_{n} = A_{n} B_{n} $$ 이다.
주기가 $T$인 수열 $\{a_{n}\}$, $\{b_{n}\}$에 대하여 $A_{n} = f_{a}\left(e^{i \frac{- 2 \pi k n}{T}}\right)$, $B_{n} = f_{b}\left(e^{i \frac{- 2 \pi k n}{T}}\right)$ 이라 하자.그리고 $C_{n}$을 푸리에 역변환 해주면 계수가 $c_{n} = \sum\limits_{k = 0}^{T - 1} a_{k} b_{n - k}$인 $T - 1$차 다항식 $f_{c_{\mathcal{F}}}(x)$를 얻을 수 있습니다.
$$ c_{n} = \sum_{k = 0}^{T - 1} a_{k} b_{n - k} $$ 이면 $C_{n} = \sum\limits_{k = 0}^{T - 1} c_{k} e^{i \frac{- 2 \pi k n}{T}} = f_{c}\left(e^{i \frac{- 2 \pi k n}{T}}\right)$에 대하여 $$ C_{n} = A_{n} B_{n} $$ 이다.
길이가 각각 $T_{a}$, $T_{b}$인 두 수열 $\{a_{n}\}$, $\{b_{n}\}$에 대하여 두 다항식 $$ \begin{align} f_{a}(x) &= a_{0} x^{0} + a_{1} x^{1} + \cdots + a_{T_{a} - 2} x^{T_{a} - 2} + a_{T_{a} - 1} x^{T_{a} - 1} \\ f_{b}(x) &= b_{0} x^{0} + b_{1} x^{1} + \cdots + b_{T_{b} - 2} x^{T_{b} - 2} + b_{T_{b} - 1} x^{T_{b} - 1} \end{align} $$ 의 곱을 $f_{c_{\mathcal{P}}}(x)$라 하면, $$ \begin{align} f_{c_{\mathcal{P}}}(x) = &\left( a_{0} b_{0} \right) x^{0} + \\ &\left( a_{0} b_{1} + a_{1} b_{0} \right) x^{1} + \\ &\left( a_{0} b_{2} + a_{1} b_{1} + a_{0} b_{2} \right) x^{1} + \cdots + \\ &\left( a_{T_{a} - 2} b_{T_{b} - 1} + a_{T_{a} - 1} b_{T_{b} - 2} \right) x^{\left( T_{a} - 1 \right) + \left( T_{b} - 1 \right) - 1} + \\ &\left( a_{T_{a} - 1} b_{T_{b} - 1} \right) x^{\left( T_{a} - 1 \right) + \left( T_{b} - 1 \right)} \\ = &\sum_{n = 0}^{\left( T_{a} - 1 \right) + \left( T_{b} - 1 \right)} \left( \sum_{k = 0}^{n} a_{k} b_{n - k} \right) x^{n} \end{align} $$ 이다.모양새가 닮긴 했지만 바로 FFT를 활용하여 곱셈하기는 힘든 모습입니다.
두 수열 $\{a_{n}\}$, $\{b_{n}\}$의 길이가 각각 $T_{a}$, $T_{b}$이다.
$2^{L - 1} \leq T_{a} + T_{b} - 1 < 2^{L}$인 자연수 $L$에 대하여 $T_{ab} = 2^{L}$이라 정의한다.
두 수열 $\left\{a^{'}_{n}\right\}$, $\left\{b^{'}_{n}\right\}$를
$$
a^{'}_{n} =
\begin{cases}
a_{n} & 0 \leq n < T_{a} \\
0 & T_{a} \leq n < T_{ab}
\end{cases}
\\
b^{'}_{n} =
\begin{cases}
b_{n} & 0 \leq n < T_{b} \\
0 & T_{b} \leq n < T_{ab}
\end{cases}
$$
이라 정의한다.
$$
\begin{align}
A^{'}_{n} &= f_{a^{'}}\left(e^{i \frac{- 2 \pi k n}{T_{ab}}}\right) \\
B^{'}_{n} &= f_{b^{'}}\left(e^{i \frac{- 2 \pi k n}{T_{ab}}}\right) \\
C^{'}_{n} &= A^{'}_{n} B^{'}_{n} \\
c^{'}_{n} &= \frac{1}{T_{ab}} \sum\limits_{k = 0}^{T_{ab} - 1} C^{'}_{k} e^{i \frac{2 \pi k n}{T_{ab}}}
\end{align}
$$
이라 한다.
FFT를 활용한 다항식 곱셈
다항식 $f_{c^{'}}(x) = \sum\limits_{k = 0}^{T_{ab} - 1} c^{'}_{k} x^{k}$에 대하여, $$ f_{c^{'}}(x) = f_{a}(x) f_{b}(x) $$ 이다.
다항식 $f_{c^{'}}(x)$는 $0 \leq n < T_{ab}$인 $T_{ab}$개의 자연수 $n$에 대하여 점
$$
\left(e^{i \frac{- 2 \pi k n}{T_{ab}}}, f_{c^{'}}\left(e^{i \frac{- 2 \pi k n}{T_{ab}}}\right) \right) = \left(e^{i \frac{- 2 \pi k n}{T_{ab}}}, f_{a^{'}}\left(e^{i \frac{- 2 \pi k n}{T_{ab}}}\right) f_{b^{'}}\left(e^{i \frac{- 2 \pi k n}{T_{ab}}}\right) \right)
$$
를 지난다. ($f_{c^{'}}(x)$의 FFT 결과가 $C^{'}$이므로)
$f_{a^{'}}(x) = \sum\limits_{k = 0}^{T_{ab} - 1} a^{'}_{k} x^{k} = \sum\limits_{k = 0}^{T_{a} - 1} a_{k} x^{k} + \sum\limits_{k = T_{a}}^{T_{ab} - 1} 0 x^{k}$ 에서 $f_{a^{'}}(x) = f_{a}(x)$이고, 마찬가지로 $f_{b^{'}}(x) = f_{b}(x)$ 이다.
다항식 $f_{a}(x) f_{b}(x)$도 $0 \leq n < T_{ab}$인 $T_{ab}$개의 점
$$
\left(e^{i \frac{- 2 \pi k n}{T_{ab}}}, f_{a^{'}}\left(e^{i \frac{- 2 \pi k n}{T_{ab}}}\right) f_{b^{'}}\left(e^{i \frac{- 2 \pi k n}{T_{ab}}}\right) \right)
$$
를 지나고, 서로 다른 점 $T_{ab}$개를 지나는 $T_{ab} - 1$차 이하의 다항식은 다항식 보간 에 의해 유일하므로, $f_{c^{'}}(x) = f_{a}(x) f_{b}(x)$이다.