CODEWITHSUNDEEP
matlabpolynomial-math
codelearner
codelearner

Reputation: 193

Code Horner’s Method for Polynomial Evaluation

I am trying to code Horner’s Method for Polynomial Evaluation but for some reason its not working for me and I'm not sure where I am getting it wrong.

These are the data I have:

nodes = [-2, -1, 1]
x = 2
c (coefficients) = [-3, 3, -1]

The code I have so far is:

function y = horner(x, nodes, c)

   n = length(c);
   y = c(1);

   for i = 2:n
       y = y * ((x - nodes(i - 1)) + c(i));
   end
end

I am supposed to end up with a polynomial such as (−1)·(x+2)(x+1)+3·(x+2)−3·1 and if x =2 then I am supposed to get -3. But for some reason I don't know where I am going wrong.

Edit:

So I changed my code. I think it works but I am not sure:

function y = horner(x, nodes, c)
   n = length(c);
   y = c(n);
   for k = n-1:-1:1
       y = c(k) + y * (x - nodes((n - k) + 1));
   end
end

Upvotes: 1

Views: 1588

Answers (2)

dmuir
dmuir

Reputation: 4431

(I'm sorry this isn't python but I don't know python)

In the case where we didn't have nodes, horner's method works like this:

p = c[n]
for i=n-1 .. 1
    p = x*p + c[i]

for example for a quadratic (with coeffs a,b,c) this is

p = x*(x*a+b)+c

Note that if your language supports fma

fma(x,y,x) = x*y+z

then horner's method can be written

p = c[n]
for i=n-1 .. 1
    p = fma( x, p, c[i])

When you do have nodes, the change is simple:

p = c[n]
for i=n-1 .. 1
    p = (x-nodes[i])*p + c[i]

Or, using fma

p = c[n]
for i=n-1 .. 1
    p = fma( (x-nodes[i]), p, c[i])

For the quadratic above this leads to

p = (x-nodes[1]*((x-nodes[2])*a+b)+c

Upvotes: 0

Avi
Avi

Reputation: 362

This works:

function y = horner(x, nodes, c)
   n = length(c);
   y = 0;
   for i = 1:n % We iterate over `c`
      tmp = c(i);
      for j = 1:i-1 % We iterate over the relevant elements of `nodes`
          tmp *= x - nodes(j); % We multiply `c(i) * (x - nodes(1)) * (x -nodes(2)) * (x- nodes(3)) * ... * (x - nodes(i -1))
      end
      y += tmp; % We added each product to y
   end
   % Here `y` is as following:
   % c(1) + c(2) * (x - nodes(1)) + c(3) * (x - nodes(1)) * (x - nodes(2)) + ... + c(n) * (x - nodes(1)) * ... * (x - nodes(n - 1))
end

Upvotes: 1

Related Questions