[알고리즘] 고속 푸리에 변환(Fast Fourier Transform) part. 1

지금까지 고속푸리에변환(이하 FFT)의 원리를 잘 모르고 썼는데 오늘 각잡고 공부해서 깨달았다.

아직 완벽히 이해한건 아닌것 같지만 잊어버리기 전에 남겨놓고자 한다.

(쓰다보니 길어져서 파트를 나누었다. part1은 필요한 지식, part2에 FFT 원리에 대해 포스팅한다.)

 

감사한 곳

https://codeforces.com/blog/entry/43499

https://codeforces.com/blog/entry/43499

 

FFT는 다항식을 빠르게 계산하는 알고리즘이다.

$A(x) = \sum_{i=0}^{n-1} a_ix^i, B(x) = \sum_{i=0}^{n-1} b_ix^i$일 때 $C(x)=A(x)B(x)$를 빠르게 구하는 알고리즘이다.

그냥 단순 알고리즘으로 구한다면 $O(n^2)$이 걸릴 것인데 FFT를 이용하면 $O(n \log n)$에 구할 수 있다.

 

이제 천천히 알아보자.

 

Point form & Coefficient form

프로그래밍 할 때 다항식을 나타내는데 우리는 주로 배열을 사용한다.

예를들어 $A(x) = x^2+2x+5$라면 $A = [1,2,5]$로 사용한다.

이렇게 나타내는 방법을 Coefficient form이라고 한다.

 

반면 미지수가 $n$개인 연립 방정식에서 식이 $n$개가 주어지면 유일한 해가 존재하는 것이 알려져있다.

$3x+2y=5$

$2x+5y=7$

은 식이 2개이고 미지수가 2개이므로 유일한 해가 존재한다.

이를 다항식에 적용해보자.

$A(x) = a_0+a_1x+a_2x^2+\dots+a_{n-1}x^{n-1}$에서 $a_0, a_1, \dots, a_{n-1}$을 찾아야 한다.

미지수가 $n$개니까 $(x_0, y_0), (x_1, y_1), \dots, (x_{n-1},y_{n-1})$을 알고 있다면 계수들을 찾을 수 있을 것이다.

$(x_0, y_0), (x_1, y_1), \dots, (x_{n-1},y_{n-1})$ 이런 식으로 나타내는 방법이 Point form이다.

 

Coefficient form -> Point form

이는 단순히 $x = 0, 1, \dots, n-1$을 대입하면 $\{(0, A(0)), (1, A(1)), \dots, (n-1, A(n-1))\}$인 Point form 을 얻을 수 있다.

$n$개의 점을 구하는데 $O(n)$이걸리기 때문에 시간 복잡도는 $O(n^2)$이 된다. (이를 FFT로 단축시킬 것이다.)

 

Point form -> Coefficient form

$A = {(x_0, y_0), (x_1, y_1), \dots, (x_{n-1},y_{n-1})}$가 주어져 있다고 하자.

$\begin{pmatrix} 1 & x_0 & x_0^2 & \dots & x_0^{n-1} \\ 1 & x_1 & x_1^2 & \dots & x_1^{n-1} \\ \dots & \dots &\dots &\dots &\dots \\ 1 & x_{n-1} & x_{n-1}^2 & \dots & x_{n-1}^{n-1} \end{pmatrix} ^ {-1} \begin{pmatrix} y_0 \\ y_1 \\ \dots \\ y_{n-1} \end{pmatrix} = \begin{pmatrix} a_0 \\ a_1 \\ \dots \\ a_{n-1} \end{pmatrix}$

이러한 연립방정식을 해결하여 구할 수 있다.($O(n^2)$)

 

다항식을 곱하는 과정

1. $A$, $B$를 point form 으로 변환 (DFT : $O(n^2)$, FFT : $O(n \log n)$)

2. $C = AB$를 수행 ($O(n)$)

3. point form 인 $C$를 coefficent form으로 되돌리기 (IDFT : $O(n^2)$, IFFT : $O(n \log n)$)

 

이제 FFT를 알아보려고 하는데 그 전에 여러가지 수학적 사실을 알아야 한다.

한번 가볍게 짚고 넘어가자.

 

복소수

$i^2 = -1$인 $i$를 허수라고 하고 이를 포함한 수 체계를 복소수라고 한다.

복소수는 $z = a+bi (a \in \mathbb{R}, b \in \mathbb{R})$로 나타낸다.

 

오일러 공식

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

$z = re^{xi}$로 하여 모든 복소수를 나타낼 수 있다.

 

De Moivre 공식

$|z| = 1$이라고 하자.(즉, $r = 1$)

$(\cos x+i \sin x)^n = \cos (nx) + i \sin (nx)$이다.

 

proof)

$z^n = (\cos x+i \sin x)^n= e^{xin} = \cos (nx) + i \sin (nx)$

 

단위 근

자연수 $n$에 대해 $z^n = 1$인 $z$를 단위 근이라고 한다.

단위 근은 $n$개 존재하고 각각 $w_1, w_2, \dots, w_n$라고 하면 $w_j^n = 1$이다.

De Moivre 공식에 의해 $w_j^n = \cos (nx) + i \sin (nx)$

$w_j^n=1$이려면 $nx = 2 \pi k$여야 한다. (삼각함수의 주기성, $k \in \mathbb{Z}$)

그러한 $x = \frac{2 \pi k}{n}$이다.

따라서 단위근은 $w_j = e^{xi} = e^{i \frac{2 \pi j}{n}}$가 된다.($j \in \{0,1,\dots,n-1 \}$)

 

앞으로 표기할 때 $w_n^k = e^{\frac{2 \pi k}{n} i}$로 표기할 것이다.

 

Lemma 1

$n \ge 0, k \ge 0, d \ge 0$ 일 때 $w_{dn}^{dk} = w_n^k$이다.

 

proof)

$w_{dn}^{dk} = e^{\frac{2 \pi dk}{dn}i} = e^{\frac{2 \pi k}{n}i} = w_n^k$

 

Lemma 2

$n > 0$이고 짝수라면 $w_n^{\frac{n}{2}} = w_2 = -1$

 

proof)

$w_n^{\frac{n}{2}} = e^{\frac{2 \pi}{n}i \frac{n}{2}} = e^{\pi i} = -1$

 

Lemma 3

$n>0$이고 짝수라면 $(w_n^k)^2 = w_{\frac{n}{2}}^k$이다. (proofed by lemma 1)

 

Lemma 4

$n \ge 0, k \ge 0$이면 $w_n^{k+\frac{n}{2}} = -w_n^k$

 

proof)

$w_n^{k+\frac{n}{2}} = e^{\frac{2 \pi}{n} i (k+\frac{n}{2})} = e^{\frac{2 \pi i}{n} k + \pi i} = e^{\frac{2 \pi i}{n}{k}} \times (-1) = -w_n^k$

 

이제 다음 파트에서 FFT를 해보도록 한다.