다항식 $A(x) = \sum_{i=0}^{n} a_i x^i$와 $B(x) = \sum_{i=0}^{m} b_i x^i$가 주어졌을 때, 두 다항식의 곱인 $C(x) = A(x)B(x)$를 구하는 문제를 생각해 봅시다. 일반적인 계수 중심의 곱셈 방식(Convolution)은 $O(nm)$의 시간 복잡도를 가집니다. 하지만 고속 푸리에 변환(FFT)을 이용하면 이를 $O(N \log N)$ 수준으로 최적화할 수 있습니다.

점-값 표현법 (Point-Value Representation)

다항식을 표현하는 또 다른 방법은 좌표 평면 위의 점들을 이용하는 것입니다. $n$차 다항식은 서로 다른 $n+1$개의 점 $(x_i, y_i)$가 주어지면 유일하게 결정됩니다. 두 다항식 $A(x)$와 $B(x)$를 점-값 표현으로 나타낸다면, $C(x_i) = A(x_i) \times B(x_i)$ 연산을 통해 곱셈 결과를 단 $O(n)$ 만에 계산할 수 있습니다.

문제는 계수 표현을 점-값 표현으로 바꾸는 과정(DFT)과 다시 계수로 되돌리는 과정(IDFT)의 복잡도입니다. 이를 해결하기 위해 복소수 평면의 '단위근(Roots of Unity)'을 활용합니다.

단위근의 성질

반지름이 1인 복소평면의 원 위에서 $n$등분 된 지점의 복소수를 단위근이라고 하며, $w_n = e^{i\frac{2\pi}{n}} = \cos(\frac{2\pi}{n}) + i\sin(\frac{2\pi}{n})$으로 정의합니다. 주요 성질은 다음과 같습니다.

• 주기성: $w_n^{k+n} = w_n^k$
• 대칭성: $w_n^{k + n/2} = -w_n^k$
• 축소성: $w_{kn}^{ki} = w_n^i$

분할 정복을 이용한 계산

다항식 $A(x)$를 짝수 차수 항들과 홀수 차수 항들로 분리하여 다음과 같이 정의할 수 있습니다.

$A_{even}(x) = a_0 + a_2x + a_4x^2 + \dots + a_{n-2}x^{n/2-1}$
$A_{odd}(x) = a_1 + a_3x + a_5x^2 + \dots + a_{n-1}x^{n/2-1}$

이를 이용하면 전체 다항식은 $A(x) = A_{even}(x^2) + x A_{odd}(x^2)$가 됩니다. 여기에 단위근 $w_n^k$를 대입하면 다음과 같은 관계식이 성립합니다.

1. $k < n/2$ 일 때: $A(w_n^k) = A_{even}(w_{n/2}^k) + w_n^k A_{odd}(w_{n/2}^k)$
2. $k \ge n/2$ 일 때: $A(w_n^k) = A_{even}(w_{n/2}^{k-n/2}) - w_n^{k-n/2} A_{odd}(w_{n/2}^{k-n/2})$

이러한 구조는 문제를 절반으로 나누어 해결하는 분할 정복 형태를 띠며, 재귀적으로 구현 가능합니다.

#include <complex>
#include <vector>
#include <cmath>

using namespace std;

typedef complex<double> Complex;
const double PI = acos(-1);

void performFFT(vector<Complex>& coeffs, bool invert) {
    int n = coeffs.size();
    if (n == 1) return;

    vector<Complex> even(n / 2), odd(n / 2);
    for (int i = 0; i < n / 2; ++i) {
        even[i] = coeffs[i * 2];
        odd[i] = coeffs[i * 2 + 1];
    }

    performFFT(even, invert);
    performFFT(odd, invert);

    double angle = 2 * PI / n * (invert ? -1 : 1);
    Complex w_unit(cos(angle), sin(angle));
    Complex w(1);

    for (int i = 0; i < n / 2; ++i) {
        Complex t = w * odd[i];
        coeffs[i] = even[i] + t;
        coeffs[i + n / 2] = even[i] - t;
        w *= w_unit;
    }
}

역 변환 (Inverse FFT)

점-값 표현에서 다시 다항식의 계수를 추출하려면 역 변환이 필요합니다. 계산 방식은 DFT와 거의 동일하지만, $w_n^k$ 대신 켤레 복소수인 $w_n^{-k}$를 사용하며 최종 결과값을 $n$으로 나누어줍니다. 위 코드에서 invert 플래그를 통해 방향을 제어할 수 있습니다.

비트 반전(Bit-Reversal)을 이용한 최적화

위의 재귀 방식은 메모리 할당과 함수 호출 오버헤드가 큽니다. 이를 방지하기 위해 '나비 연산(Butterfly operation)'과 '비트 반전' 배열을 사용하여 반복문 형태의 반복적 FFT(Iterative FFT)를 구현하면 성능을 더욱 끌어올릴 수 있습니다.

void fastConvolution(vector<long long>& a, vector<long long>& b, vector<long long>& res) {
    vector<Complex> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    int n = 1;
    while (n < a.size() + b.size()) n <<= 1;
    fa.resize(n);
    fb.resize(n);

    performFFT(fa, false);
    performFFT(fb, false);
    
    for (int i = 0; i < n; ++i) fa[i] *= fb[i];
    
    performFFT(fa, true);
    res.resize(n);
    for (int i = 0; i < n; ++i) {
        res[i] = (long long)(fa[i].real() / n + 0.5);
    }
}

이와 같이 FFT를 활용하면 매우 큰 차수의 다항식 곱셈이나 큰 수의 곱셈을 효율적으로 처리할 수 있으며, 이는 신호 처리, 이미지 압축 등 다양한 알고리즘의 근간이 됩니다.