다항식의 계수 배열·덧셈·곱셈

3 + 2x + 5x²처럼 x의 거듭제곱에 수를 곱해 더한 식을 다항식(polynomial)이라고 합니다. 다항식은 수학 시간에만 나오는 것이 아니라, 롤링 해시에서 문자열을 수로 바꿀 때도, 화면에 매끄러운 곡선을 그릴 때도, 전송 중 망가진 데이터를 바로잡는 오류 정정 부호에서도 쓰입니다. 컴퓨터로 다항식을 계산하려면 먼저 식을 어떤 자료로 담을지 정해야 합니다. 이 글에서는 리스트의 위치가 차수를 뜻하도록 다항식을 담고, 값을 계산하는 방법과 두 다항식을 더하고 곱하는 방법을 구현합니다.

계수를 차수 순서로 담기

다항식 3 + 2x + 5x²에서 각 항의 x에 곱해진 수 3, 2, 5를 계수(coefficient)라 하고, x의 지수 0, 1, 2를 그 항의 차수(degree)라고 합니다. 계수가 0이 아닌 항 가운데 가장 큰 차수를 다항식의 차수라고 하므로, 이 다항식은 2차입니다. 이 교재에서는 계수를 낮은 차수부터 리스트에 담아, 인덱스 i에 xⁱ의 계수를 둡니다. 그러면 3 + 2x + 5x²는 [3, 2, 5]입니다.

이 방법에서는 계수가 0인 항도 자리를 지켜야 합니다. 1 + 4x²에는 x항이 없지만, 리스트로는 [1, 0, 4]라고 적어야 4가 인덱스 2, 곧 x²의 계수가 됩니다. 가운데 0을 빼고 [1, 4]라고 적으면 1 + 4x라는 다른 다항식이 됩니다. 계수의 값뿐 아니라 계수가 놓인 위치가 뜻을 가지는 것입니다.

반대로 리스트 끝에 붙은 0은 다항식의 값을 바꾸지 않습니다. [1, 0, 4, 0]도 1 + 4x² + 0x³이라 [1, 0, 4]와 같은 다항식입니다. 같은 다항식이 여러 모양의 리스트로 나타나면 두 리스트를 비교하거나 차수를 읽을 때 헷갈리므로, 계산 결과는 끝의 0을 지운 모양으로 정리하기로 합니다. 모든 계수가 0인 영다항식은 빈 리스트가 되지 않도록 [0]으로 둡니다. 입력으로는 빈 리스트도 영다항식으로 받아 줍니다.

교재나 도구에 따라 높은 차수부터 담는 경우도 있습니다. 어느 쪽이든 괜찮지만, 한 프로그램 안에서 두 방식을 섞으면 같은 리스트가 전혀 다른 다항식을 뜻하게 되므로 처음에 정한 방향을 끝까지 지켜야 합니다.

값 계산하기: 호너의 방법

x에 수를 넣어 다항식의 값을 구할 때, 항마다 x의 거듭제곱을 따로 계산하면 곱셈이 많이 듭니다. 3 + 2x + 5x²를 다음과 같이 묶어 쓰면 곱셈이 차수만큼으로 줄어듭니다.

3 + 2x + 5x² = 3 + x × (2 + x × 5)

안쪽부터 계산하면, 5에서 시작해 x를 곱하고 다음 계수 2를 더하고, 다시 x를 곱하고 다음 계수 3을 더하면 됩니다. 가장 높은 차수의 계수부터 "x를 곱하고 다음 계수를 더한다"를 되풀이하는 이 방법을 호너의 방법(Horner's method)이라고 합니다. n차 다항식이면 곱셈과 덧셈을 n번씩만 합니다.

이 계산은 어디선가 본 적이 있습니다. 롤링 해시에서 문자열의 해시값을 만들 때 h = h * base + ord(글자)를 되풀이했는데, 이것이 바로 글자 코드를 계수로 하는 다항식에 x = base를 넣어 호너의 방법으로 계산한 것입니다.

같은 차수끼리 더하기

두 다항식을 더할 때는 차수가 같은 항끼리 계수를 더합니다. 리스트로는 같은 인덱스의 값끼리 더하면 되고, 한쪽이 더 짧으면 그쪽에 없는 높은 차수의 계수는 0으로 봅니다. (3 + 2x + 5x²) + (1 - 5x² + 4x³)을 계산해 보겠습니다.

결과 [4, 2, 0, 4]는 4 + 2x + 4x³입니다. 2차 계수가 0이 되었지만 가운데에 있는 0이므로 지우지 않습니다. (1 + 2x) + (-1 - 2x)처럼 모든 계수가 사라지면 [0, 0]이 되는데, 끝의 0을 정리하면 영다항식 [0]이 됩니다.

차수가 더해지는 곱셈

두 다항식을 곱할 때는 분배법칙에 따라 첫 다항식의 모든 항과 둘째 다항식의 모든 항을 하나씩 곱한 뒤, 차수가 같은 항끼리 모읍니다. 항 a·xⁱ와 b·xʲ를 곱하면 (a × b)·xⁱ⁺ʲ이 되므로, 리스트로는 결과의 인덱스 i + j에 a × b를 더하면 됩니다. 여러 쌍의 곱이 같은 차수로 모일 수 있으므로, 그 칸에 값을 덮어쓰지 않고 계속 더해야 합니다.

(1 + 2x) × (3 + 4x)를 계산하면 다음과 같습니다.

1차 계수에는 4x와 6x의 두 곱이 함께 모여 10이 되었습니다. 길이가 m과 n인 리스트를 곱하면 가장 큰 인덱스가 (m - 1) + (n - 1)이므로, 결과 리스트는 m + n - 1칸으로 준비합니다. 이렇게 두 리스트의 값을 인덱스의 합이 같은 것끼리 모아 더하는 연산을 합성곱(convolution)이라고도 부릅니다.

def normalize(coefficients):
    result = list(coefficients) or [0]
    while len(result) > 1 and result[-1] == 0:
        result.pop()
    return result


def polynomial_add(first, second):
    result = [0] * max(len(first), len(second), 1)
    for i, coefficient in enumerate(first):
        result[i] += coefficient
    for i, coefficient in enumerate(second):
        result[i] += coefficient
    return normalize(result)


def polynomial_multiply(first, second):
    if not first or not second:
        return [0]
    result = [0] * (len(first) + len(second) - 1)
    for i, a in enumerate(first):
        for j, b in enumerate(second):
            result[i + j] += a * b
    return normalize(result)


def evaluate(coefficients, x):
    value = 0
    for coefficient in reversed(coefficients):
        value = value * x + coefficient
    return value


print(polynomial_add([3, 2, 5], [1, 0, -5, 4]))
print(polynomial_add([1, 2], [-1, -2]), polynomial_add([], []))
print(polynomial_multiply([1, 2], [3, 4]), polynomial_multiply([], [1, 2]))
print(evaluate([3, 2, 5], 2), evaluate([3, 2, 5], 0))

[4, 2, 0, 4]
[0] [0]
[3, 10, 8] [0]
27 3

list(coefficients) or [0]은 복사한 리스트가 비어 있으면 [0]을 쓰라는 뜻입니다. or는 왼쪽 값이 빈 리스트처럼 거짓으로 여겨지는 값이면 오른쪽 값을 돌려주기 때문입니다. evaluate는 호너의 방법을 그대로 옮긴 것으로, reversed로 높은 차수의 계수부터 읽습니다. x = 2를 넣으면 3 + 2 × 2 + 5 × 4 = 27이고, x = 0이면 상수항 3만 남습니다.

왜 맞는가

덧셈은 결과의 인덱스 i에 두 다항식의 xⁱ 계수를 모두 더하므로, 차수가 같은 항끼리 더한다는 정의와 같습니다. 곱셈은 두 반복으로 첫 다항식의 항 i와 둘째 다항식의 항 j의 모든 쌍을 정확히 한 번씩 곱하고, 그 곱을 차수 i + j의 칸에 더합니다. 분배법칙으로 전개하면 바로 이 항들이 나오고, 같은 차수의 항을 모으는 것이 칸에 더하는 일이므로 결과가 다항식의 곱과 같습니다.

정리 단계는 리스트 끝의 0만 지우고, 리스트가 하나만 남으면 멈춥니다. 끝의 0은 가장 높은 차수에 0을 곱한 항이라 지워도 다항식의 값이 바뀌지 않고, 가운데의 0은 건드리지 않으므로 나머지 계수의 차수도 그대로입니다. 반복할 때마다 길이가 하나씩 줄어 끝납니다.

비용과 다른 표현

계수가 m개와 n개인 두 다항식의 덧셈은 O(m + n), 곱셈은 모든 항의 쌍을 곱하므로 O(mn)입니다. 호너의 방법은 차수에 비례하는 O(n)입니다. 계수가 큰 정수이거나 실수라면 연산 한 번의 비용이나 반올림 오차도 따로 생각해야 합니다.

이 표현은 계수 대부분이 0이 아닐 때 알맞습니다. x¹⁰⁰⁰⁰⁰⁰ + 1처럼 차수는 높고 항은 몇 개 없는 다항식을 담으려면 1000001칸짜리 리스트에 0이 999999개 들어갑니다. 이런 다항식은 {1000000: 1, 0: 1}처럼 차수를 키, 계수를 값으로 하는 딕셔너리로 담는 편이 낫습니다. 인접 행렬과 인접 목록에서 칸 대부분이 0인 표 대신 이웃 목록을 쓴 것과 같은 판단입니다.

더 깊이: 더 빠른 곱셈

두 n차 다항식의 곱셈은 모든 항의 쌍을 곱하는 방법으로 O(n²)이지만, 이보다 빠른 방법이 있습니다. 1960년 Anatoly Karatsuba는 각 다항식을 낮은 차수 절반과 높은 차수 절반으로 나누면, 네 번 필요해 보이는 절반 크기의 곱셈을 세 번으로 줄일 수 있음을 보였습니다. 이것을 분할 정복으로 되풀이하면 곱셈에 드는 시간이 n의 약 1.585제곱에 비례하는 정도로 줄어듭니다. 정수도 자릿수를 계수로 보면 다항식과 같으므로, CPython은 매우 큰 정수를 곱할 때 이 Karatsuba 방법을 씁니다.

더 나아가 고속 푸리에 변환(fast Fourier transform, FFT)을 쓰면 다항식의 곱셈을 O(n log n)에 할 수 있습니다. 계수를 그대로 곱하는 대신 여러 점에서의 값으로 바꾸어 곱하고 다시 계수로 되돌리는 방법으로, 신호 처리와 아주 큰 수의 곱셈에 널리 쓰입니다. 이 교재에서 직접 구현하지는 않지만, 같은 계산도 자료를 다른 모양으로 바꾸어 보면 훨씬 빨라질 수 있다는 좋은 예입니다.

정리

• 다항식은 인덱스 i에 xⁱ의 계수를 두는 리스트로 나타내며, 계수가 0인 가운데 항도 자리를 지켜야 차수가 맞습니다.
• 끝의 0은 값을 바꾸지 않으므로 계산 결과에서 지우고, 영다항식은 [0]으로 둡니다.
• 호너의 방법은 높은 차수의 계수부터 x를 곱하고 다음 계수를 더해 n차 다항식의 값을 O(n)에 구하며, 롤링 해시의 계산과 같습니다.
• 덧셈은 같은 인덱스끼리 더하는 O(m + n)이고, 곱셈은 모든 항의 쌍의 곱을 인덱스 i + j에 더해 모으는 O(mn)입니다.
• 항이 적고 차수가 높은 다항식은 차수를 키로 하는 딕셔너리가 알맞고, 큰 곱셈에는 Karatsuba 방법이나 FFT 같은 더 빠른 방법이 있습니다.

연습 문제

1. 차수가 다른 두 다항식 더하기

2x³ + 1을 이 교재의 계수 리스트로 적고, -2x³ + 3x와 더한 결과를 리스트와 식으로 쓰세요.

2. 가운데 0을 지우면

[4, 2, 0, 4]에서 가운데 0을 지워 [4, 2, 4]로 만들면 어떤 다항식이 되나요?

3. 1차 항이 사라지는 곱셈

(1 + x) × (1 - x)를 계수 리스트로 곱하고, 1차 계수가 0이 되는 이유를 설명하세요.

다음 글 행렬의 모양·덧셈·곱셈에서는 위치를 두 개의 인덱스로 나타내는 수의 표, 곧 행렬을 다루고, 행과 열을 짝지어 곱하는 행렬 곱셈을 구현합니다.