계산기는 다항식을 어떻게 빨리 계산할까 · 조립제법과 나머지정리
곱셈 10번이 필요해 보이는 4차식을 곱셈 4번으로 끝낸다
- 10 → 4 4차식 한 번 계산에 드는 곱셈 횟수
- f(3) = 130 x − 3으로 나눈 나머지와 같다
- 55 → 10 10차식이라면
계산기와 컴퓨터는 사인, 로그 같은 값을 구할 때 그 함수에 아주 가까운 다항식을 대신 계산하는 경우가 많다. 그러니 다항식 하나를 얼마나 적은 계산으로 끝내느냐가 곧 속도다. 컴퓨터에게 곱셈은 덧셈보다 비싼 일이라, 곱셈의 횟수를 센다.
조립제법의 표는 나눗셈의 요령이기 전에, 다항식의 값을 가장 적은 곱셈으로 구하는 순서다.
f(x) = 2x⁴ − 3x³ + 5x² − x + 7에 x = 3을 넣어 보자. 적힌 대로 항마다 거듭제곱을 따로 만들면 2x⁴에 곱셈 4번, 3x³에 3번, 5x²에 2번, x항에 1번, 모두 10번이 든다. 계산하면 162 − 81 + 45 − 3 + 7 = 130이다.
식을 f(x) = (((2x − 3)x + 5)x − 1)x + 7로 묶으면 안쪽부터 「곱하고 더하기」를 네 번 하면 된다. 2에서 시작해 2 × 3 − 3 = 3, 3 × 3 + 5 = 14, 14 × 3 − 1 = 41, 41 × 3 + 7 = 130. 곱셈은 4번뿐이다. 이 방법을 호너법이라 부르는데, 교과서의 조립제법과 똑같은 계산이다. 조립제법 표의 아랫줄에 차례로 나오는 2, 3, 14, 41, 130이 바로 이 수들이다.
그래서 조립제법은 두 가지를 한 번에 준다. 아랫줄의 마지막 수 130은 f(3)이고, 동시에 f(x)를 x − 3으로 나눈 나머지다. 나머지정리가 말하는 그대로다. 앞의 네 수 2, 3, 14, 41은 몫 2x³ + 3x² + 14x + 41의 계수다. 차수가 n인 다항식이라면 적힌 대로 계산할 때 곱셈이 n(n + 1) ÷ 2번이지만 호너법은 n번이다. 10차식이면 55번과 10번의 차이다. 교과서에서 나눗셈을 빨리 하는 요령으로 배운 표가, 기계 안에서는 다항식의 값을 구하는 가장 빠른 방법으로 쓰인다.