C언어 수치계산 - 다항식 계산 알고리즘 (호너법 Horner's method)

 

 

본 글에서는 호너법을 이용해 다항식을 계산하는 알고리즘과 간단한 예시를 소개한다.

 

호너법이란?

 

출처 Wikipedia Horner's method

일반적으로 다항식은 첫째줄과 같이 풀어져있는 형태이다.

저걸 두번째줄 처럼 괄호 안에 식이 들어있고 또 그 안에 식이 들어있고.. 하는 형태로 바꾼 것이다.

프로그래밍은 반복되는 것을 좋아한다. 둘째 줄에서 간단히 알고리즘 패턴을 읽어낼 수 있다.

 

호너법을 이용한 다항식 계산 알고리즘

 

1. x를 입력한다

2. y₀ = a₀ 이라고 한다.

3. j = 1,2,...,n 순으로 다음식을 계산한다. y_j = y_j-1x + a_j

 

이제 이걸 C언어로 작성해보자.

식은 다음 예제를 사용했다.

 

출처 GeeksForGeeks Horner's Method

참고로 변수 nt랑 na는 호너법과 식 그대로 계산하는 경우 필요한 계산 횟수를 비교하기 위해 넣은 변수라 지워도 무관하다.

 

	//polynomial algorithm in C
	#include <stdio.h>
	int main(void)
	{
	// 값입력: 다항식 차수에 따라 변경할 것
	float a[4], y[4];
	a[0] = 2.0;
	a[1] = -6.0;
	a[2] = 2.0;
	a[3] = -1.0;
	int n = 3; //다항식의 차수
	//Algorithm Step1. x를 입력한다
	printf("Input x: ");
	float x;
	scanf("%f", &x);
	//Algorithm Step2. y0=a0
	y[0] = a[0];
	//Algorithm Step3. j=1,2,...,n 순으로 계산한다
	int nt = 0;
	int na = 0;
	int j;
	for (j = 1; j <= n; j++)
	{
	y[j] = y[j - 1] * x + a[j];
	nt++; //곱한 횟수
	na++; //더한 횟수
	}
	printf("호너법을 이용한 계산 결과\n");
	printf("P(%f)= %f \n", x, y[n]);
	printf("Multiplication: %d \n", nt);
	printf("Addition: %d \n", na);
	// 식을 그대로 계산한 경우
	nt = 0; // 곱셈, 덧셈 횟수 초기화
	na = 0;
	// x, x제곱, x의3제곱 .. x의n제곱까지 먼저 구해서 배열에 저장
	float xx[4];
	xx[1] = x;
	for (j = 2; j <= n; j++)
	{
	xx[j] = xx[j - 1] * x;
	nt++;
	}
	// x의 1승인 항 부터 계산
	float P = a[n];
	for (j = n - 1; j >= 0; j--)
	{
	P = P + a[j] * xx[n - j];
	nt++;
	na++;
	}
	printf("그대로 계산한 경우\n");
	printf("P(%f)= %f \n", x, y[n]);
	printf("Multiplication: %d \n", nt);
	printf("Addition: %d \n", na);
	return 0;
	}

view raw Horner's-Method.c hosted with ❤ by GitHub

실행결과

 

 

보다시피 호너법을 이용한 경우가 계산 횟수가 더 적은 걸 알 수 있다.

다항식의 차수가 늘어날수록 그 차이는 더 커진다.

 

📚 Reference 

- 数値計算入門「C言語版」 / サイエンス社　

- Horner's Method for Polynomial Evaluation / Geeks For Geeks 

- Horner's method / Wikipedia