Tuesday, October 26, 2010

Horner scheme - Evaluating a polynomial in O(n) complexity

#include
using namespace std;

double evaluate( double *coeffs, int n, double x )
{
        double val = coeffs[n]*x;
        for( int i = n-1 ; i > 0 ; i-- )
                val = (val + coeffs[i])*x;
        val += coeffs[0];
        return val;
}

int main()
{
        int n;
        cout << "Enter the degree::";
        cin >> n;
        double *coeffs = new double[n+1];
        for( int i = 0 ; i <= n ; i ++ )
        {
                cout << "Enter the coefficient of "<< i <<"th degree term::";
                cin >> coeffs[i];
        }

        double prev, x;
        cout << "Enter the value at which polynomial needs to be evaluated::";
        cin >> x;
        do
        {
                cout << evaluate( coeffs, n, x ) << endl;
                prev = x;
                cout << "Enter the value at which polynomial needs to be evaluated::";
                cin >> x;
        }while(prev!=x);

        delete [] coeffs;
}