FFT 알고리즘 이해해보기

목차

이 글은 작성 중입니다.

city입니다. 알고리즘을 오래 해온 것 치고 모르는 고급 알고리즘이 많은데, Lawali님이 FFT를 설명하는 것을 우연히 보고 이해한 것을 한번 정리해봅니다.

1. 개요

FFT를 잠시 머리에서 지우고 두 다항식의 곱을 구하는 것을 생각해 보겠습니다. 다음과 같은 상황에서 f(x)g(x)f(x)g(x)를 구하는 겁니다.

f(x)=a0+a1x+a2x2++an1xn1f(x) = a_0 + a_1x + a_2x^2 + \cdots + a_{n-1}x^{n-1} g(x)=b0+b1x+b2x2++bm1xm1g(x) = b_0 + b_1x + b_2x^2 + \cdots + b_{m-1}x^{m-1}

가장 단순히 구현했을 때 다음과 같은 코드가 될 것이고 시간복잡도는 O(nm)O(nm)이 됩니다. 편의상 각 다항식의 계수가 vector<int>로 주어진다고 가정하겠습니다.

vector<int> multiply(const vector<int>& a, const vector<int>& b) {
    vector<int> c(a.size() + b.size() - 1, 0);
    for (int i = 0; i < a.size(); i++) {
        for (int j = 0; j < b.size(); j++) {
            c[i + j] += a[i] * b[j];
        }
    }
    return c;
}

이를 더 빨리 할 수 있는 방법은 없을까요? 다항식을 다른 방식으로 나타낼 수 있는 방법을 한번 생각해 보겠습니다.

1.1. 다항식의 표현

우리는 위에서 f(x)f(x)a0+a1x+a2x2++an1xn1a_0 + a_1x + a_2x^2 + \cdots + a_{n-1}x^{n-1}로 나타냈습니다. 이는 벡터 a=(a0,a1,,an1)a=(a_0, a_1, \cdots, a_{n-1})가 있으면 다항식 f(x)f(x)를 유일하게 결정할 수 있다는 것을 의미합니다.

다른 방식은 없을까요? 당연히 있습니다. n1n-1차 다항식이 있다고 하면 그 n1n-1차 다항식은 서로 다른 xx값을 갖는 nn개의 점에서의 값만 알면 유일하게 결정됩니다. 예를 들어 f(x)f(x)가 2차 다항식이라고 하면 3개의 값인 f(0),f(1),f(2)f(0), f(1), f(2)를 알면 f(x)f(x)를 유일하게 결정할 수 있습니다.

그럼 우리는 n1n-1차 다항식 f(x)f(x)m1m-1차 다항식 g(x)g(x)를 곱한 nm2n-m-2차 다항식 f(x)g(x)f(x)g(x)에 대해서, 이 f(x)g(x)f(x)g(x)의 서로 다른 n+m1n+m-1개의 점에서의 값만 알 수 있다면 f(x)g(x)f(x)g(x)를 유일하게 결정할 수 있습니다. 이를 이용해서 더 빠르게 곱셈을 할 수 있지 않을까요?

어떤 방법을 써서든 n1n-1차 다항식 f(x)f(x)nn개의 점에서의 값으로 나타내고 또 반대로 하는 걸 빠르게 할 수 있다면 우리는 다항식 곱셈을 빠르게 할 수 있습니다! 그 방법이 바로 FFT입니다.

2. FFT 시행

앞서 n1n-1차 다항식에 대해 nn개의 서로 다른 xx값을 갖는 점에서의 값을 알 수 있다면 그 다항식을 유일하게 결정할 수 있다고 했습니다. 그런데 이 값은 서로 다르기만 하면 어떤 값이든 상관이 없습니다. 이는 우리가 계산을 빨리 할 수 있는 형태로 정하기만 하면 된다는 뜻입니다.

우리가 여기서 할 것은 n1n-1차 다항식을 nn개의 서로 다른 값에서의 점을 이용해 나타내는 형태로 변환하는 것입니다.

우리는 이를 분할 정복으로 해결할 것이고, 따라서 계산상의 편의를 위해 먼저 nn이 2의 제곱수라고 가정하겠습니다. 그렇지 않은 경우에는 남는 항들의 계수를 0으로 채워서 nn을 2의 제곱수로 만들어 주면 됩니다.

2.1. 분할 정복

먼저 n=2kn = 2^k차 다항식 f(x)f(x)를 두 부분으로 나누어 보겠습니다. 짝수 차수 항들과 홀수 차수 항들로 나누어 볼 수 있는데요. 그럼 f(x)f(x)를 이런 형태로 나타낼 수 있습니다.

f(x)=(a0+a2x2+a4x4++an2xn2)+x(a1+a3x2+a5x4++an1xn2)=fe(x2)+xfo(x2)wherefe(x)=a0+a2x+a4x2++an2xn/21fo(x)=a1+a3x+a5x2++an1xn/21f(x) = (a_0 + a_2x^2 + a_4x^4 + \cdots + a_{n-2}x^{n-2}) + x(a_1 + a_3x^2 + a_5x^4 + \cdots + a_{n-1}x^{n-2}) = f_e(x^2) + xf_o(x^2) where f_e(x) = a_0 + a_2x + a_4x^2 + \cdots + a_{n-2}x^{n/2-1} f_o(x) = a_1 + a_3x + a_5x^2 + \cdots + a_{n-1}x^{n/2-1}

그리고 fe(x)f_e(x)fo(x)f_o(x)는 각각 n/2n/2차 다항식이 됩니다. 즉 각각에 대해서도 똑같은 방식으로 나누어 줄 수 있습니다.

이를 계속 반복하게 되면 우리는 처음에 n=2kn = 2^k로 가정했으므로 최후에는 0차 다항식 즉 상수들만 남게 될 겁니다. 상수에 대해서는 다항식 -> 점으로 변환하는 것을 바로 할 수 있습니다.

하지만 이렇게만 계산하는 건 오히려 시간복잡도를 늘립니다. 뭔가 분할 정복을 통해 더 빠르게 계산할 수 있는 방법이 있을 것 같습니다.

앞서 정한 fe(x)f_e(x)fo(x)f_o(x)도 서로 다른 x값에서의 점 n/2n/2개를 이용해 나타낼 수 있습니다. 각각이 갖는 서로 다른 x값들을 x0,x2,,xn/22x_0, x_2, \cdots, x_{n/2-2} 그리고 x1,x3,,xn/21x_1, x_3, \cdots, x_{n/2-1}로 나누겠습니다.

이때 다음 조건을 만족한다면 어떻게 될까요?

x02=x12x22=x32xn/222=xn/212x_0^2 = x_1^2 x_2^2 = x_3^2 \cdots x_{n/2-2}^2 = x_{n/2-1}^2

2.2. 복소수의 사용

참고

https://blog.naver.com/kks227/221633584963