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는 호너법과 식 그대로 계산하는 경우 필요한 계산 횟수를 비교하기 위해 넣은 변수라 지워도 무관하다.

 

실행결과

 

 

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

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

 

📚 Reference 

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

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

- Horner's method / Wikipedia