다항식과 계수 배열
핵심 질문
다항식 곱셈은 왜 배열 곱셈처럼 보일까?
교과서 설명
다항식은 1,x,x2,x3,… 같은 항을 계수와 함께 더한 식이다.
A(x)=a0+a1x+a2x2+⋯+am−1xm−1
이 다항식은 계수만 모아서 배열로 저장할 수 있다.
[a0,a1,a2,…,am−1]
예를 들어
A(x)=1+2x+3x2
는 다음 배열과 같다.
[1,2,3]
계수 배열에서 i번 칸은 xi 앞에 붙은 숫자를 뜻한다. 그래서 0번 칸은 상수항, 1번 칸은 x의 계수, 2번 칸은 x2의 계수다.
다항식은 특정 값에 대입해서 계산할 수도 있다.
A(2)=1+2⋅2+3⋅22=17
FFT에서는 다항식을 두 가지 모습으로 본다. 하나는 계수 배열이고, 다른 하나는 여러 점에 대입해 얻은 값들의 배열이다. DFT와 FFT는 이 두 모습을 빠르게 오가는 도구로 볼 수 있다.
앞 장에서는 DFT를 다항식 평가로도 읽을 수 있다고 정리했다. 이제 그 다항식 언어를 조금 더 자세히 보자. 신호 배열 x[n]을 다항식의 계수로 놓으면
A(z)=x[0]+x[1]z+x[2]z2+⋯+x[N−1]zN−1
이고, DFT는 이 다항식에 단위원근을 하나씩 넣어 보는 계산이다.
여기서 단위원근은 일단 앞 장의 DFT에서 쓰던 회전값이라고 생각하면 된다. 정식 정의와 성질은 단위원근 장에서 원시 단위원근, 반 바퀴 대칭, 직교합으로 다시 증명한다.
A(ωNk)=n=0∑N−1x[n](ωNk)n=X[k]
그래서 “신호를 주파수 점수표로 바꾼다”는 말과 “다항식을 여러 점에서 평가한다”는 말은 같은 계산을 다른 언어로 설명한 것이다.
계수 표현과 값 표현
다항식은 두 가지 방식으로 저장할 수 있다. 첫 번째는 계수 표현이다.
A(x)=a0+a1x+⋯+adxd
이 표현은 각 항의 재료를 직접 들고 있는 방식이다. 두 번째는 값 표현이다. 서로 다른 점 x0,x1,…,xd에 대해
A(x0),A(x1),…,A(xd)
를 저장하는 방식이다.
차수가 d 이하인 다항식은 서로 다른 d+1개의 점에서의 값을 알면 하나로 결정된다. 이것이 보간 interpolation의 기본 정리다. 직관적으로는 미지수 d+1개인 계수를 찾기 위해 방정식 d+1개가 필요하다고 볼 수 있다.
왜 그런지도 짧게 볼 수 있다. 두 다항식 P(x), Q(x)가 차수 d 이하이고 서로 다른 d+1개의 점에서 값이 같다고 하자. 그러면 차이
R(x)=P(x)−Q(x)
는 그 d+1개의 점에서 모두 0이 된다. 하지만 0이 아닌 차수 d 이하의 다항식은 서로 다른 근을 최대 d개만 가질 수 있다. 따라서 R(x)는 영다항식이고, 결국 P(x)=Q(x)다.
FFT 곱셈은 이 두 표현 사이를 빠르게 오가는 방법이다.
계수 표현FFT값 표현
값 표현에서는 곱셈이 쉬워진다.
C(xj)=A(xj)B(xj)
모든 점 xj에서 위 식이 성립하므로, 충분히 많은 점에서 값을 구한 뒤 역변환하면 곱한 다항식의 계수로 돌아올 수 있다. DFT가 단위원근에서의 평가라는 사실은 FFT가 왜 다항식 곱셈에 쓰이는지 설명하는 핵심 연결고리다.
주의할 점은 점의 개수다. 두 다항식의 차수가 각각 m−1, n−1이면 곱의 차수는 최대 m+n−2다. 따라서 계수는 m+n−1개 필요하고, FFT 길이도 적어도 이만큼은 되어야 한다.
직관 비유
레시피를 생각하자. 밀가루 1컵, 설탕 2컵, 달걀 3개처럼 재료의 양만 적어도 요리를 다시 만들 수 있다. 다항식의 계수 배열도 각 항에 들어가는 “재료의 양”을 순서대로 적은 것이다.
예제
다항식 두 개를 곱해 보자.
(1+2x)(3+4x)
모든 조합을 곱하면
1⋅3+1⋅4x+2x⋅3+2x⋅4x
같은 차수끼리 모아서
3+10x+8x2
가 된다. 배열로 쓰면 다음과 같다.
[1,2]×[3,4]⇒[3,10,8]
가운데 10은 x가 한 번 나오는 조합을 모두 더한 값이다.
10=1⋅4+2⋅3
손풀이 체크
-
2+5x+7x2의 계수 배열은?
답 보기
[2,5,7]
-
계수 배열 [4,0,1]은 어떤 다항식일까?
답 보기
4+x2
-
(1+x)(2+3x)의 x 계수는?
답 보기
1⋅3+1⋅2=5
다음으로 이어지는 생각
다항식 계수들이 곱해져 새 계수를 만드는 규칙이 바로 다음 장의 합성곱과 같은 모양이다.
계수 배열 [a0,a1,a2]로 다항식 값 A(x) 계산하기
#include <iostream>
#include <vector>
using namespace std;
int evaluate(const vector<int>& coefficients, int x) {
int value = 0;
int power = 1;
for (int coefficient : coefficients) {
value += coefficient * power;
power *= x;
}
return value;
}
int main() {
vector<int> coefficients = {1, 2, 3};
cout << "A(2) = " << evaluate(coefficients, 2) << "\n";
}
연습: 계수를 [2,5,7]로 바꾸고 A(2)를 손으로 먼저 계산해 보자.