Horner’s Method

Introduction

If you love polynomials, you will love this article. We all know how to evaluate a polynomial at a given point i.e. say you got a polynomial , and you would like to compute . Well, it’s a plug-and-play. Just substitute and evaluate. Simple right ? Right. The problem is for a polynomial of degree , we need multiplications and additions. This article introduces you to Horner’s Method, named after William George Horner, which evaluates a polynomial in a fast way. It is economic as Horner’s method requires only additions and Floor() mutiplications.

Horner’s Method

Let be a polynomial of degree as follows

(1)  

(2)  

(3)  

(4)  

MATLAB implementation

Next, we present the function HornersMethod.m implements this idea, where input is the degree of the polynomial , the vector is an vector containing coefficients , and , the point which we which to find which is the output “out”.

function [out] = HornersMethod(n,x,t)
% initialize first elements=
out = x(1);
% apply Horners at point t for coefficients x of a 
% polynomial of degree n
for j = 2:n
    out = out*t + x(j);
end

Summary

This article demonstrates Horner’s method, as well as its MATLAB implementation. Indeed, Horner’s method is provides efficiency as operations is required vs the naive implementation, which needs .

Finally, Subscribe to my channel to support us ! We are very close to 100K subscribers <3 w/ love. The algorithmic chef – Ahmad Bazzi. Click here to subscribe. Check my other articles here.

[paypal_donation_block email=’myprivateotherstuff@gmail.com’ amount=’3.00′ currency=’USD’ size=’large’ purpose=’Buy me coffee ^^’ mode=’live’]

PS: I’m on twitter. I retweet stuff around algorithms, python, MATLAB and mathematical optimization, mostly convex.