//----------------------------------------------------------------------

//

// Time-stamp: <30/01/01 00:43 Kenneth L Moore>

//

// :File: horner.cpp

// :Purpose: implement brute force and horner polynomial evaluation method

//----------------------------------------------------------------------

//----------------------------------------------------------------------

// includes

#include <cstdlib>

//----------------------------------------------------------------------

// typedefs, globals

//----------------------------------------------------------------------

// function declarations

float eval_polynomial_brute( float C[], int n, float x );

float eval_polynomial_Horner( float C[], int n, float x );

//----------------------------------------------------------------------

// function definitions

/*

Brute force method of computing a polynomial. Does unnecessary multiplications

of powers of x.

C is a float array of coeffients. The last element is the coefficient of x**n

n is the order of the polynomial equation.

x is the point at which to evaluate the function.

*/

float eval_polynomial_brute( float C[], int n, float x ){

float y = 0.0;

for(int e = 0; e <=n; e++){

y = y + C[e]*pow(x,e);

}

return y;

}

/*

Implements a more efficient solution that relies on algebra to rearrange

the terms so that no power of x is ever done more than once.

C is a float array of coeffients. The last element is the coefficient of x**n

n is the order of the polynomial equation.

x is the point at which to evaluate the function.

*/

float eval_polynomial_Horner( float C[], int n, float x ){

float y = C[n];

for(int index = n-1; index >= 0; index--){

y = y*x + C[index};

}

return y;

}

//----------------------------------------------------------------------

int main(int argc, char *arg[]) {

return EXIT_SUCCESS;

}

// eof

/******************************************************************************

Analysis:

A polynomial is f(x) = c[0]*x**0 + c[1]*x**1 + c[2]*x**2 ... c[n]*x**n

To do the brute force method x must be multiplied x**n; x**n-1; ... x**2;

(x**n is n-1 multiplications). So in brute force we need n-1 + n-2 + ... 1

multiplications.

To do the horner method, since there is an algebraic mainpulation.

c[0] + x*(c[1] + x(c[2] + ... + x(c[n]) we never do a redundant multiplication

of x so we need only do n-1 multiplications.

*******************************************************************************/