고속 푸리에 변환(FFT, Fast Fourier Transform)은 이산 푸리에 변환(DFT)을 O(n log n)에 계산하는 알고리즘이다. 두 다항식의 곱셈을 O(n log n)으로 처리하거나 대용량 수의 곱셈, 신호 처리에 활용된다.
핵심 원리
Cooley-Tukey 알고리즘: n=2^k 크기 DFT를 홀수·짝수 인덱스로 분할 정복한다.
DFT(n) = DFT_even(n/2) + w^k * DFT_odd(n/2)
(w = e^(2πi/n), 원시 n제곱근)
구현 (다항식 곱셈)
python
import cmath
def fft(a, invert=False):
n = len(a)
if n == 1: return
# 비트 역전 순열
j = 0
for i in range(1, n):
bit = n >> 1
while j & bit:
j ^= bit; bit >>= 1
j ^= bit
if i < j: a[i], a[j] = a[j], a[i]
# 버터플라이 연산
length = 2
while length <= n:
ang = 2 * cmath.pi / length * (-1 if invert else 1)
wlen = cmath.exp(1j * ang)
for i in range(0, n, length):
w = 1
for k in range(length // 2):
u, v = a[i+k], a[i+k+length//2] * w
a[i+k] = u + v
a[i+k+length//2] = u - v
w *= wlen
length <<= 1
if invert:
for i in range(n): a[i] /= n
def multiply(p1, p2):
result_len = 1
while result_len < len(p1) + len(p2):
result_len <<= 1
fa = [complex(x) for x in p1] + [0]*(result_len-len(p1))
fb = [complex(x) for x in p2] + [0]*(result_len-len(p2))
fft(fa); fft(fb)
for i in range(result_len): fa[i] *= fb[i]
fft(fa, invert=True)
return [round(x.real) for x in fa]
관련 개념
