내가 찾는 고속 푸리에 변환(FFT)은 알고리즘 문제 풀이를 해결하기 위한 FFT인데, 찾아보는 자료마다 이것 저것 푸리에 변환에 대한 공식이 적혀있고, Numpy를 이용해서 FFT 그래프를 그리고 해석하는 등 데이터 분석에 필요한 FFT 구현을 위주로 설명이 되어 있었다.
그런 FFT 그래프 구현 등은 다른 블로그 등에서 매우 잘 다룬 자료들이 많으므로 다루지 않을 거고, 내가 다룰 내용은 FFT 알고리즘을 구현하여 문제를 풀 수 있도록 (백준 등) 고속 푸리에 변환 (FFT)과 고속 푸리에 역변환 (IFFT)를 내용으로 작성함 (코드 첨부)
고속 푸리에 변환(FFT)
📌고속 푸리에 변환?
고속 푸리에 변환(FFT)란 이산 푸리에 변환(DFT)을 빠르게 진행하기 위해 만들어낸 알고리즘
DFT는 입력 신호에 대한 푸리에 변환으로, 디지털 신호 분석을 위해 사용
❓ FFT 를 이용해서 DFT를 진행하면 얻는 이점?
다항식의 곱을 계산할 시 굉장히 오랜 시간이 소요
👀 FTT를 생각하지 않고 다항식의 곱을 구해보자 두 다항식A(x) = x² + 3x + 2, B(x) = 2x²+1을 곱해서 C(x)를 만든다고 가정해보자. 일반적으로 우리는 C(x) = A(x)*B(x) = (x²+3x+2)(2x²+1) = x²(2x²+1) + 3x(2x²+1) + 2(2x²+1) = 2x⁴ + x² + 6x³ +3x + 4x² +2 = 2x⁴ +6x³+5x²+3x+2의 과정을 거쳐서 C(x)를 구한다.
컴퓨터는 계산하기 위해서 A(x) = 2 + 3x + x² → A=[2, 3, 1] , B(x) = 1+2x² → B=[1, 0, 2] 에서 A*B → C = [2, 3, 5, 6, 2]를 통해 C(x) =2+3x+5x²+6x³+2x⁴의 과정을 거쳐서 C(x)를 구한다 즉 A(x) = a0 + a₁x + a₂x³+ ... + anxⁿ , B(x) = b0 + b₁x + b₂x³+ ... + bnxⁿ의 연산을 통해 C(x) = c0 + c₁x + c₂x³+ ... + c₂nx²ⁿ를 얻게되고, 이때 시간 복잡도는 O(n²)의 시간이 소요된다.
이를 행렬로 표현하면 다음과 같이 표현할 수 있다. 출처 : 위키피디아
이러한 복잡한 계산을 푸리에 변환을 이용하면 다항식의 곱을 굉장히 빠른 속도로 구할 수 있음
반응형
❓그럼 어떻게 적용할 수 있을까?
우함수와 기함수의 특징을 활용해서 식을 2등분을 할 수 있음.
👀 기함수와 우함수의 특징을 생각해보자 y(x) = x²란 함수가 있다면, (1, 1), (2,4) ... 이런식으로 값들을 구할 수도 있겠지만, 우함수의 특징(y(x) = y(-x))을 이용하면 (1,1)의 값에서 (-1,1)도 구할 수 있고 (2,4)에서 (-2,4)의 값도 자연스레 알 수 있다. y(x) = x³란 함수가 있다면, (1, 1), (2,8) ... 이런식으로 값들을 구할 수도 있겠지만, 기함수의 특징(y(x) = -y(-x))을 이용하면 (1,1)의 값에서 (-1,-1)도 구할 수 있고 (2,4)에서 (-2,-4)의 값도 자연스레 알 수 있다.
그렇다면 y(x) = 3x^5 + 2x⁴ + x³ + 7x²+5x+1란 숫자를 변형해보자 y(x) = (2x⁴+7x²+1) + x(3x⁴+x²+5)로 식을 변형 할 수 있고, 이때 y1(x²) = (2x⁴+7x²+1), y2(x²)= (3x⁴+x²+5)라고 하면 y(xi) = y1(xi²) + xi*y2(xi²) 식과 기함수의 특징으로 y(-xi) = y1(xi²) - xi*y2(xi²) 식 두개를 얻을 수 있다. 즉, 이런 과정을 거치면 다항식의 차수를 (n//2 - 1)차로 낮출 수 있다(5차 → 2차)
P(x) = p0 + p₁x + p₂x³+ ... + pnxⁿ 에서의 해가 ±x₁, ±x₂, ±x₃, ... ±xn/2 라하면 P(x) = P1(x²)+xP2(x²)의 형태로 변형 할 수 있고 우함수의 성질을 이용하여 P(xi) = P1(xi²)+xP2(xi²) P(-xi) = P1(xi²)-xP2(xi²) 로 변형하여 해를 [P(x₁),P(-x₁), ... ,P(xn/2),P(-xn/2)] 를 얻을 수 있다. 이 때 시간 복잡도는 O(nlogn)의 시간이 소요된다. 이를 활용하여 계산을 진행한다. (뒤에 원을 그려서 삼각함수를 따지고.. 등등 복잡한 부분은 일단 생략)
쿨리-튜키(Cooley - Tukey) 알고리즘을 사용해서 계산
쿨리-튜키 알고리즘은 FFT 결과를 계산하는 가장 일반적으로 사용되는 알고리즘 표본의 크기를 M이라할 때 M = 2이면 출처 : https://ghebook.blogspot.com/2022/10/fast-fourier-transform.html
p = 998244353 # 적당히 큰 소수
def fft(a, inverse): # 리스트를 입력받아 수행(True면 FFT의 역변환, False면 FFT를 통한 DFT)
n = len(a)
j = 0
for i in range(1,n): # 입력 신호의 시간축 정보를 뒤집어서 변환
reverse = n // 2
while j >= reverse:
j -= reverse
reverse //= 2
j += reverse
if i < j:
a[i], a[j] = a[j], a[i]
# Cooley-Tukey 알고리즘
step = 2
while step <= n:
half = step // 2 # 현재 단계 절반
u = pow(3, p//step, p) # 원시근의 제곱 수
if inverse: # 역변환을 수행해야 할 경우
u = pow(u, p-2,p) # 페르마의 소정리 이용
for i in range(0, n, step): #나비 도표를 계산하는 과정
w = 1
for j in range(i, i + half):
v = a[j + half] * w
a[j + half] = (a[j] - v)% p
a[j] = (a[j]+v) % p
w = (u*w) % p
step *= 2
if inverse: # 역변환 수행시 변환 과정
num = p - (p-1) // n
for i in range(n):
a[i] = (a[i] * num) %p
x = [1,2,3,4]
fft(x,False) # FFT 변환
print(x) # [10, 173167434, 998244351, 825076915]
fft(x,True) # FFT 역변환
print(x) # [1, 2, 3, 4]
댓글