<사고력 훈련 문제 #1>: Horner의 법칙

# Horner의 법칙 문제 //horner의 법칙 관련 개념 설명은 맨 밑에 있습니다. 

---

 문제) Horner의 법칙은 주어진 점 $x0$ 에서 최소의 곱으로 다항식 $A(x) = a_nx^n+a_{n-1}x^{n-1}+\ldots+a^1x+a_0$ 를 계산하는 것으로 이 법칙은

$A(x_0) = ( ... ((a_nx_0 + a_{n-1})x_0 + ... + a_1)x_0 + a_0)$

이다. Horner의 법칙을 사용하여 다항식을 계산하는 C프로그램을 작성하라.

# 풀이

---

 Horner의 법칙 문제를 풀 때는 직접 손으로 먼저 계산하며 그 과정을 이해해야 한다. 곱셈으로 도출된 값이 다음 덧셈에 이용되고 또 그렇게 도출된 나머지가 곱셈되어 다음 덧셈에 이용되는 그 과정을 이해해야 한다.

/*************************************************
 ** Horner의 법칙 문제 소스코드
*************************************************/

// Horner's rule: 최소의 곱으로 다항식 계산
#include <stdio.h>

/* 각 항의 계수를 나타내는 a, 옆의 숫자는 변수의 차수다. */
/* a0, a1, a2, a3, ... , a(n) */

double arr[] = { 1,2,3,4,5 };
/* 1 + 2x + 3x^2 + 4x^3 + 5x^4 다항식(polynomial) 생성*/

// n의 크기를 갖는 다항식 poly에 x를 대입한 결과를 반환하는 horner_rule 함수
double horner_rule(int n, int x, double *poly);

void main()
{
	int size, x; // size: 다항식의 수, x: x0의 값
	double result; // 결과값을 저장하는 용도

	// 변수 초기화

	x = 2; // 다항식 f(x)에 2를 대입한 결과 f(2)를 구하는 과정이다.
	size = sizeof(arr) / sizeof(double); // 다항식의 항의 갯수 저장

	result = horner_rule(size, x, arr);
	printf("Polynomail's result = %.2f\n", result);
}

double horner_rule(int n, int x, double *poly)
{
	double res = 0;
	int i;

	// n번의 곱셈과 n번의 덧셈으로 결과 산출하는 것이 horner법칙의 핵심개념

	for (i = 0; i < n; i++)
	{
		// 한 번의 곱과 덧셈으로 이루어진 과정이 n - 1번 이루어진다.
		// 항이 5개인 다항식은 4번의 덧셈과 곱셉만으로 결과값을 추출할 수 있다.
		res = res*x + poly[n - i - 1];  // res는 곱셈과 덧셈을 반복하며 점차 값이 커진다.

		printf("f(%d) = %.2f\n", i, res); // 과정을 출력
	}
	return res;
}

/*************************************************
 ** End Line
*************************************************/

# Horner's rule 이란?

---

 Horner의 법칙은 어떻게 하면 다항식의 연산 횟수를 최소화 시킬 수 있을까? 라는 고민으로부터 탄생했다. 밑의 예로 주어진 다항식을 통해 어떻게 Horner의 법칙이 도출되는지 직접 확인해보자. // 아래와 같이 중간에 비는 차수 없이 쭈욱 나열되어 있는 다항식에만 Horner의 법칙이 적용된다.

$f(x) = 4x^4 + 5x^3 + 6x^2 + 7x + 8$

 첫 번째로 생각해야할 점은 이 다항식에는 총 몇 번의 덧셈과 곱셉 연산이 이루어지는지에 대해서다. 이 다항식은 4번의 덧셈과 10번의 곱셈으로 이루어져있다. 덧셈같은 경우 수식에 바로 드러나 있듯이 4번 등장하고, 곱셉의 경우 변수 x의 차수들을 더하면 10이라는 숫자가 나온다.

 다항식이 최고차항부터 순서대로 나열되어 있으므로 곱셈의 횟수를 계산할 때는 $\sum_{i=0}^n  i = \frac{n(n+1)} {2}$ 공식을 이용하여 계산할 수 있다. 덧셈의 경우 최고차항의 차수만 알면 몇 번 덧셈이 이루어지는지 알 수 있다. 예시로 보고 있는 다항식의 경우 4차 이므로, 4번 덧셈이 이루어진다.

 두 번째로는 저 연산횟수를 어떻게하면 최소화시킬 수 있을까? 에 대해 생각해야 한다. 결론부터 말하면 n차 다항식의 덧셈과 곱셈연산은 n번의 덧셈과 n번의 곱셈으로 구성할 수 있다. 아래의 도출 과정을 살펴보자.

• $f(x) = 4x^4 + 5x^3 + 6x^2 + 7x + 8$
  
  
• = $x(4x^3 + 5x^2 + 6x + 7)+8$
  
  
• = $x(x(4x^2+5x+6)+7)+8$
  
  
• = $x(x(x(4x+5)+6)+7)+8$

 위의 도출과정을 통해 4번의 덧셈과 4번의 곱셈으로 연산횟수를 줄이는데 성공했다. 위의 도출된 식을 바탕으로 계산하는 과정을 살펴보면 아래와 같다. 입력값 x는 5라고 가정한다.

$f(x) = 4x^4 + 5x^3 + 6x^2 + 7x + 8$

 먼저 최고차항부터 계수별로 나열을 한다. 최고차항의 계수 4는 입력값 5와 곱셈을 하지 않은 채 그대로 내려온다. 그리고 4와 입력값 5를 곱해준다. 그 결과가 20이고 다음차수의 계수 5와 덧셈을 한다. 덧셈의 결과 25와 입력값 5를 또 한 번 곱한다. 그 결과인 125와 다음차수의 계수인 6과 곱한다. 이런 과정을 반복하다 보면 f(5)의 값 3318을 얻을 수 있다.