WAP Horner Rule

coefficients := [-19, 7, -4, 6] # list coefficients of all x^0..x^n in order
x := 3
accumulator := 0
for i in length(coefficients) downto 1 do
# Assumes 1-based indexing for arrays
accumulator := ( accumulator * x ) + coefficients[i]
done
# accumulator now has the answer



A fast scheme for evaluating a polynomial such as:

-19+7x-4x^2+6x^3,

when

x=3;.

is to arrange the computation as follows:

((((0) x + 6) x + (-4)) x + 7) x + (-19;

And compute the result from the innermost brackets outwards as in this pseudocode:


#include

double horner(double *coeffs, int s, double x)
{
int i;
double res = 0.0;

for(i=s-1; i >= 0; i--)
{
res = res * x + coeffs[i];
}
return res;
}


int main()
{
double coeffs[] = { 3.0, 2.0, 1.0, 1.0 };

printf("%5.1f\n", horner(coeffs, sizeof(coeffs)/sizeof(double), 2.0));
return 0;
}

TC O(n)
SC O(1)
Run Here https://ideone.com/uGAZC