Horner's role

알고리즘 수업시간에 배운걸 끄적인다.

고차 다항식 계산을 프로그램에 적용한다면

몇몇 사람들은 식 그대로 사용할 지도 모른다.

예를 들어서.. 10x^3+5x^2+3x+6 = y 라는 식이 존재한다고 하면

C언어 기준으로 

int main()
{
    int x = 10;
    int y = 10*x*x*x + 5*x*x + 3*x + 6;
    printf("y is %d\n",y);
    return 0;
}

라고 작성할 수 있다.(일부는 라이브러리를 사용하여 제곱 계산을 할 수도 있겠지만..)

하지만 Horner's role을 사용하여 계산 횟수를 줄일 수 있다.

식을 묶어버린다면,

(10x^2+5x+3)x+6 

=((10x+5)x+3)x+6

으로 변한다.

식을 다시 작성해 본다면

int main()
{
    int x = 10;
    int y = ((10*x+5)*x+3)*x+6;
    printf("y is %d\n",y);
    return 0;
}

요렇게 바뀐다.

첫 번째 코드는 연산이 곱셈 6번, 덧셈 3번

두 번째 코드는 연산이 곱셈 3번, 덧셈 3번

곱셈이 무려 3번이나 줄어들었다.