FFT와 빠른 다항식 곱셈

FFT(Fast Fourier Transform)는 다항식을 계수 표현에서 특수한 점들, 즉 복소 원시 단위근의 거듭제곱에서의 값 표현으로 빠르게 바꾸는 Divide-and-Conquer 알고리즘이다. 계수끼리 직접 convolution하면 두 차수 n-1 다항식 곱셈은 \(\Theta(n^{2})\)Θ(n²)이지만, FFT로 값 표현으로 바꾸고 점별로 곱한 뒤 IFFT로 돌아오면 전체가 \(\Theta(n \log n)\)Θ(n log n)이다.

계수 표현 → \(\text{FFT} \to \)FFT →점별 곱셈\((\text{pointwise} \text{multiplication}) \to \)(pointwise multiplication) →역 \(\text{FFT}(\text{IFFT}) \to \)FFT(IFFT) →결과 계수 순서로 진행한다. 전체 시간은 \(\Theta(n \log n)\)Θ(n log n)+\(\Theta(n)\)Θ(n)+\(\Theta(n \log n)\)Θ(n log n)=\(\Theta(n \log n)\)Θ(n log n)이다.

FFT가 metaheuristic인지, real-only인지, primitive root를 쓰는지, polynomial multiplication runtime을 줄이는지 묻는 문장은 category와 precondition부터 확인한다.

• II-18

II부는 정답을 정확히 2개 고르는 방식\((\text{exactly}_{\text{two}})\)(exactly(two))이다. A~D 중 두 개를 선택해야 한다.

정답 암기가 아니라 FFT가 무엇을 변환하고, 왜 복소 단위근을 쓰며, 다항식 곱셈의 어느 단계가 \(\Theta(n^{2})\)Θ(n²)에서 \(\Theta(n \log n)\)Θ(n log n)으로 줄어드는지 판정하게 한다.

목록에 적힌 원본 파일명은 문자 깨짐이 있지만, 로컬 파일과 코퍼스 조각을 통해 복원 시험 자료가 AuD Gedächtnisprotokoll SoSe 2025.md임을 확인했다. 독일어 움라우트는 의미가 명확한 곳만 복원했다.

강의 7의 17~18쪽에서는 길이 n인 계수 배열을 곱셈에 필요한 2n개 점에서 평가하므로 FFTWrap에 2n차 원시근을 사용한다. 연습문제 12의 G3은 n개 점 평가에 n차 원시근을 사용한다. 따라서 'FFT가 n차 원시근을 쓴다'는 진술은 DFT/FFT의 일반 사실로 맞지만, 다항식 곱셈에서는 보통 2n개 또는 최소 2n-1개의 충분한 평가점을 골라야 한다.

계수 표현에서 다항식 곱셈을 하면 각 계수 조합을 모두 더하는 convolution이라 느리다. FFT의 핵심은 문제를 더 쉬운 표현으로 옮기는 것이다. 여러 x값에서 p(x), q(x)를 이미 알고 있으면 \(r(x)=p(x)q(x)\)r(x)=p(x)q(x)는 각 점에서 그냥 곱하면 된다. 어려운 부분은 많은 점에서 빠르게 값을 구하고 다시 계수로 돌아오는 일인데, 복소 원시 단위근을 고르면 even/odd 분할이 재사용되어 Divide-and-Conquer가 된다.

고속 푸리에 변환(FFT, Fast Fourier Transform)은 이산 푸리에 변환(DFT)을 \(\Theta(n \log n)\)Θ(n log n)에 계산하는 알고리즘이다. DFT는 계수 벡터 \(a_{0},...,a_{n-1}\)a₀,...,aₙ-1}를 원시 n차 단위근 ω_n의 거듭제곱에서 평가한 값 벡터로 바꾼다. 원시 m차 단위근(primitive m-th root of unity)은 ω_\(m^{m}=1\)mᵐ=1이고 \(1\le j<m\)1≤j<m에서는 ω_\(m^{j}\)m^j≠1을 만족하며, 복소수에서는 ω_\(m=\text{exp}(2\)m=exp(2πi/m)=cos(2π/m)+i sin(2π/m)로 쓸 수 있다. 점-값 표현(point-value representation)은 서로 다른 \(x_{j}\)xⱼ에 대한 쌍 \((x_{j},p(x_{j}))\)(xⱼ,p(xⱼ))로 다항식을 나타내는 방식이다.

• 복소수 i와 exp(2πi/n)
• 다항식 차수와 2n-1개의 점이 필요한 이유
• 분할 정복 점화식(Divide-and-Conquer recurrence)
• Θ 표기

짝수·홀수 차수 분할은 \(p(x)=p_{\text{even}}(x^{2})+x p_{\text{odd}}(x^{2})\)p(x)=p(even)(x²)+x p(odd)(x²)로 쓴다. 원시근은 제곱했을 때 짝을 이루는 성질이 있어 절반 크기 부분문제가 같은 평가점을 재사용한다. 점별 곱셈(pointwise product)을 하려면 p와 q를 반드시 같은 x 좌표에서 평가해야 한다. 또한 차수가 최대 m-1인 다항식은 서로 다른 m개의 점-값 쌍으로 유일하게 결정된다.

차수가 n-1인 두 다항식을 계수 합성곱으로 직접 곱하면 \(\Theta(n^{2})\)Θ(n²)이다. FFT 평가는 점화식 \(T(n)=2T(n/2)+\Theta(n)\)T(n)=2T(n/2)+Θ(n)에서 \(\Theta(n \log n)\)Θ(n log n)이 된다. 충분한 길이로 0을 채운 뒤 변환된 값을 점별로 곱하는 단계는 \(\Theta(n)\)Θ(n)이다. 역 FFT(IFFT)는 마지막에 n으로 나누는 단계까지 포함해 \(\Theta(n \log n)\)Θ(n log n)이므로, FFT 기반 다항식 곱셈 전체도 \(\Theta(n \log n)\)Θ(n log n)이다.

차수가 n-1인 두 다항식의 곱은 차수가 최대 2n-2이므로 서로 다른 값이 최소 2n-1개 필요하다. 강의에서는 계산을 단순하게 하려고 2n개 점을 사용한다. n이 2의 거듭제곱이 아니면 0 계수를 덧붙이는 패딩(padding)을 사용할 수 있으며, 이는 점근 복잡도를 바꾸지 않는다. 원시근은 일반적으로 복소수이고, FFT는 휴리스틱 탐색이 아니라 정확한 대수 변환이다.

• ausschließlich
• keine komplexen Zahlen
• Metaheuristik
• primitive Einheitswurzel
• vom Grad n-1
• reduziert
• \(\Theta(n^{2})\)Θ(n²)
• \(\Theta(n \log n)\)Θ(n log n)

FFT는 DFT를 \(\Theta(n \log n)\)Θ(n log n)에 계산하는 Divide-and-Conquer algorithm이다.

계수 표현에서 직접 다항식을 곱하면 \(\Theta(n^{2})\)Θ(n²)이지만, FFT 기반 곱셈은 \(\Theta(n \log n)\)Θ(n log n)이다.

두 degree n-1 다항식의 product degree는 2n-2라서 최소 2n-1 points가 필요하고, 강의는 보통 2n 및 power-of-two padding을 쓴다.

메타휴리스틱이라는 설명은 거짓, 실수만 쓴다는 설명도 거짓이다. 원시근을 사용한다는 설명과 실행시간을 줄인다는 설명은 참이다.