Finance/numerical methods

Horner's Rule

Gu Youn 2009. 10. 27. 23:11
1. 설명
다항식을 빠르게 계산하는 방법 중 하나



위의 식을 아래처럼 정리하여 a_{n-1} + a_n x 부터 역으로 계산하면 다항식의 값을 구할 수 있다.


2. 코드
    
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define POWERS 10

int main(int argc, _TCHAR* argv[])
{

    double coefficients[POWERS],result[POWERS];
    double sum = 0.0;
    double variable_x=2;

    srand(1000);

    for(int n=0; n < POWERS ; n++)
    {
        coefficients[n] = rand()%50;
        result[n] = coefficients[n];

        printf("%d = %g \n",n,coefficients[n]);
    }

    //horner's rule
    sum = 0;
    for(int n=POWERS-1; n > 0 ; n--)
    {
        sum = ( sum + coefficients[n])*variable_x;
    }

    sum += coefficients[0];
    printf("horner's rule : %g\n",sum);

    //normal
    sum = 0.0;
    for(int n=0; n < POWERS ; n++)
    {
        sum = sum + result[n] * pow(variable_x, n);
    }

    printf("polynomial : %g\n",sum);
  
    return 0;
}


3. 참고자료
http://en.wikipedia.org/wiki/Horner_scheme