MATH-05. 컴퓨터로 다항식 나누기: 다항식 장제법, 조립제법

컴퓨터로 다항식의 나눗셈을 수행하는 대표적인 알고리즘은 다항식 장제법(Polynomial Long Division)과 조립제법(Synthetic Division)을 컴퓨터 코드로 구현하는 것입니다. 이 중 장제법은 일반적인 경우에 모두 사용될 수 있는 범용적인 방법이며, 조립제법은 나누는 식이 1차식일 때 매우 효율적입니다.

다항식 장제법 (Polynomial Long Division)

다항식 장제법은 우리가 손으로 다항식을 나누는 방법과 동일한 원리를 컴퓨터로 구현한 것입니다. 이 알고리즘의 핵심은 최고차항을 반복적으로 소거하는 것입니다.

알고리즘 순서

두 다항식 A(x) (피제수)와 B(x) (제수)가 주어졌을 때, 몫 Q(x)와 나머지 R(x)를 구하는 과정은 다음과 같습니다. (A(x) = B(x)Q(x) + R(x))

1. 초기화: 몫 Q(x)와 나머지 R(x)를 0으로 초기화합니다. 나머지 R(x)는 피제수 A(x)와 같다고 설정하고 시작합니다.
2. 반복 조건 확인: 나머지 R(x)의 차수가 제수 B(x)의 차수보다 크거나 같은 동안 아래 과정을 반복합니다.
3. 최고차항 비교 및 몫 계산:
• 나머지 R(x)의 최고차항을 제수 B(x)의 최고차항으로 나눕니다. 이 결과가 몫의 새로운 항(t(x))이 됩니다.
• 예: R(x) = 5x^3 + 2x^2 + …이고 B(x) = x^2 + …이면, t(x) = 5x^3/x^2 = 5x가 됩니다.
4. 몫 누적: 계산된 항 t(x)를 전체 몫 Q(x)에 더합니다. (Q(x) = Q(x) + t(x))
5. 나머지 갱신: 현재 나머지 R(x)에서 t(x) · B(x)를 뺍니다. 이 과정을 통해 R(x)의 최고차항이 소거됩니다. (R(x) = R(x) - t(x) · B(x))
6. 종료: 반복이 끝나면, 그때의 Q(x)가 최종 몫이고 R(x)가 최종 나머지가 됩니다.

예시

A(x) = x^3 - 2x^2 + x - 5를 B(x) = x - 2로 나누는 경우:

• 1단계: R(x) = x^3 - 2x^2 + x - 5, Q(x) = 0
• 2단계:
• t(x) = x^3 / x = x^2
• Q(x) = x^2
• R(x) = (x^3 - 2x^2 + x - 5) - x^2(x - 2) = x - 5
• 3단계:
• t(x) = x / x = 1
• Q(x) = x^2 + 1
• R(x) = (x - 5) - 1(x - 2) = -3
• 종료: R(x)의 차수(0)가 B(x)의 차수(1)보다 작으므로 종료합니다.
• 결과: 몫 Q(x) = x^2 + 1, 나머지 R(x) = -3

조립제법 (Synthetic Division)

조립제법은 나누는 식이 x - c 형태의 1차식일 때 계수만을 이용하여 나눗셈을 빠르고 간결하게 수행하는 알고리즘입니다.

알고리즘 순서

피제수 A(x)의 계수 배열 poly_coeffs와 제수 x - c의 값 c가 주어졌을 때 과정은 다음과 같습니다.

1. 계수 배열 준비: 피제수 A(x)의 계수들을 내림차순으로 배열에 저장합니다.
2. 초기화: 결과 배열(몫의 계수가 될 부분)의 첫 번째 값은 피제수의 첫 번째 계수와 동일하게 설정합니다.
3. 반복 계산:
• 이전 단계에서 계산된 결과값에 c를 곱합니다.
• 이 값을 피제수의 다음 차수 계수와 더하여 결과 배열의 다음 위치에 저장합니다.
• 이 과정을 피제수의 마지막 계수까지 반복합니다.
4. 결과 해석:
• 결과 배열의 마지막 값을 제외한 나머지 값들이 몫의 계수가 됩니다.
• 결과 배열의 마지막 값이 나머지가 됩니다.

예시

A(x) = x^3 - 2x^2 + x - 5를 B(x) = x - 2로 나누는 경우 (c = 2):

• 피제수 계수: [1, -2, 1, -5]
• 계산 과정:
1. 첫 번째 계수 1을 그대로 내립니다. → 결과: [1]
2. 2 * 1 = 2를 다음 계수 -2와 더합니다. → -2 + 2 = 0 → 결과: [1, 0]
3. 2 * 0 = 0을 다음 계수 1과 더합니다. → 1 + 0 = 1 → 결과: [1, 0, 1]
4. 2 * 1 = 2를 다음 계수 -5와 더합니다. → -5 + 2 = -3 → 결과: [1, 0, 1, -3]
• 결과:
• 몫의 계수: [1, 0, 1] → 1x^2 + 0x + 1 = x^2 + 1
• 나머지: -3

이처럼 컴퓨터는 다항식을 계수들의 배열 또는 리스트로 표현하고, 위와 같은 알고리즘을 통해 덧셈, 뺄셈, 곱셈, 나눗셈의 기본 연산을 반복 수행하여 다항식의 나눗셈을 처리합니다.