Horner's algorithm is a method used to evaluate a polynomial at a certain value x by separating the polynomial into monomials (A monomial is a polynomial with only one term. It can have multiple variables and a higher degree e.g. 2x^3wv).
We usually start evaluating from the monomial with the highest degree. The result obtained is added to the monomial of the next degree and so on till the lowest degree at x^0 which evaluates to 1. Horner's algorithm is recursive by nature, as we apply the result of the previous monomial to the current one.
A polynomial is expressed as
Or
f(x) = a0 + a1x + a2 x^2 + ... + a n x^n
a is co-efficient of x
n is highest degree of x
k is dynamic degree of x from 0 to the nth degree.
See the algorithm below:
- Make k = n
- set bk=ak
- bk-1=ak-1 + bkx0
- K=k-1
- If k ≥ 0, go back to step 3 else end. Where x0=x, b=result of monomial.
Step 3 of the algorithm is the recursive case.
The else part of step 5 is our base case.
A polynomial of the 3rd degree will be
f(x) = a0 + a1x + a2 x^2 + a3x^3
Let us see an example below
Example
Evaluate the polynomial
f(x)=2x^3 + 4x^2 + 3
where x = 3
following the algorithm
step 1: k=3
step 2:
b3=a3
a3=2
b3=2
step 3:
b2=a2 + b3x0
b2=4 + (2*3)
b2=10
step 4:
k=2-1
k=1
Back to step 3:
b1=a1 + b2x0
b1 = 0 + (10*3)
b1 = 30
step 4:
k=1-1
k=0
Back to step 3:
b0=a0 + b1x0
b0 = 3 + (30*3)
b0 = 93
step 4:
K=0-1
k=-1
end
Therefore the sum of our polynomial is 93
Read more on Horner's algorithm here Horner's algorithm
Now unto the web application that was built following Horner's algorithm.
Building The Frontend Logic
To achieve user interaction, we will be taking user input. So we need the following.
- Input field to take the value of x.
- Input field to enter co-efficients of x.
- A button to submit each entry.
- We need a display where users can read from, we will use an HTML paragraph element for this.
- We are also going to display instructions on how to use the app following Horner's algorithm principles.
You can go ahead to view the source code here source code,
otherwise keep reading to get a full explanation.
Since Horner's method is iterative as well as recursive, we aim to gather the co-efficients of x in an array, let us call that array polynomial.
let polynomial=[]
Some HTML code:
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="stylesheet" href="style.css">
<title>polynomial calculator</title>
</head>
<body>
<header><hr>CALCULATOR FOR POLYNOMIAL EVALUATION<hr></header>
<p id="instruct">Enter co-efficients of x from largest degree(power)to lowest degree(power of zero) in first box<hr> </p>
<p id="note"> Note:enter 0 as coefficient for degrees not present.<br /> ..<span>Example:2x^4+x^2+1</span></p>
<h2>METHOD<hr></h2>
<p id="entertwo"> Enter 2 as coefficient of x^4,enter 0 as coeffiecient of x^3 since it is not present and 1 as coefficient of x^2,<br/>
then the last 1 as it is a coeffiecent of x to power 0.<span><br/>2x^4 + 0*(x^3)+1*(x^2)+0*(x^1)+1*(x^0)</span>
<br>click on enter coefficient after each entry and enter value of x in next box,then click on sum polynomial when all is done.
<br>click on display to view coefficients</p>
<div class="forarray">
<label for="topush">Enter coefficients of x </label>
<input id="topush" type="number">
<label for="tosub" id="sub">Enter value of x</label>
<input id="tosub" type="number">
</div>
<p id="toread"></p>
<div class="choices">
<button id="but1">enter coefficient</button>
<button id="but2">display</button>
<button id="but3">sum polynomial </button>
</div>
</body>
<script src="script.js"></script>
</html>
Some JavaScript code:
let polynomial=[]
let y=polynomial.length
Let tosub=document.getElementById("tosub")
let topushA=document.getElementById("topush")
let choices=document.querySelector(".choices")
let coefficients=topushA.value
let button=document.querySelector("button")
let toread=document.getElementById("toread")
We declared our elements from the DOM in the code above.
We entered the co-efficients of x in the input field with the id topush and named the variable topushA.
We enter the value of x in the input field with id tosub. We declared a variable and named it coefficients, which is any value entered in the topush input field.
y is the length of our array which is polynomial.length. We have 3 buttons wrapped in a div class called choiceswhich we will be adding eventListeners to.
The p tag with the id of toread is where user input will be displayed.
We will use the event delegation method to add an event listener to the buttons
and use switch case for each button click condition. We will be having three case conditions in our switch, since we have 3 buttons. Each click will trigger some block of code.
/*event delegation*/
choices.addEventListener("click",clicked)
function clicked(e){
if(e.target.matches("button")){
var button=e.target
switch(button){
/*enter x coefficients*/
case but1:
coefficients=topushA.value
toread.innerHTML=coefficients+ " " + "is added "
polynomial.push(+coefficients)
break;
/*display*/
case but2:
n=polynomial.length
coefficients =polynomial[i]
toread.innerHTML="coefficients of powers of x are:<br/>"
for(var i=0;i<n;i++){
toread.innerHTML+=polynomial[i] + " "
}
break;
}
}
}
At the moment, we only have two cases.
Case 1 triggers the array push method. We click this button whenever we add a coefficient of x in our input box , this then adds the coefficient to our polynomial array.
case 2 triggers our for loop to display the coefficients of x which are the values of the array. We click this button to make sure we entered the correct values.
Now we need to trigger a button that will sum up the polynomial. Under this scenario we will utilize Horner's principle.
let polynomial=[]
var y=polynomial.length
var tosub=document.getElementById("tosub")
let topushA=document.getElementById("topush")
let choices=document.querySelector(".choices")
let coefficients=topushA.value
var button=document.querySelector("button")
let toread=document.getElementById("toread")
/*event delegation*/
choices.addEventListener("click",clicked)
function clicked(e){
if(e.target.matches("button")){
var button=e.target
switch(button){
/*enter x coefficients*/
case but1:
coefficients=topushA.value
toread.innerHTML=coefficients+ " " + "is added "
polynomial.push(+coefficients)
break;
/*display*/
case but2:
n=polynomial.length
coefficients =polynomial[i]
toread.innerHTML="coefficients of powers of x are:<br/>"
for(var i=0;i<n;i++){
toread.innerHTML+=polynomial[i] + " "
}
break;
/*sum polynomial*/
//applying principle of Horner's algorithm
case but3:
function Horner(polynomial){
var y= polynomial.length
if( i==y) return;
result = polynomial[i]+(unknown* result)
i++
Horner(polynomial)
}
let unknown=tosub.value
var i = 1
let result= polynomial[0]
Horner(polynomial )
toread.innerHTML="The sum of the polynomial is:" + result
break;
}
}
}
Our third case triggers the sum of our polynomial.
We declared a variable which we called unknown
var unknown=tosub.value
Where unknown is x, since the input field with id of tosub is where we enter the value of x. We initialized var i as 1, since we will use it to iterate the array, in this case polynomial.
We also defined a function with polynomial as parameter. We declared a variable
var result and initialized it with polynomial[0]. This is equivalent to step 2 of Horner's algorithm where we set bk = ak. This is initializing b with the coefficient of the highest degree of x. b is result,
polynomial[0] is coefficient of highest degree of x. We then increment i until it reaches base condition of i==y where y=polynomial.length.
We then have the recursive call which continues as long as our base condition is not reached.
Conclusion
We have learnt about Horner's algorithm, used in discrete maths, and how it can be applied in programming, by building a polynomial evaluator.
To test it out, you can check out the links below.
- view source code
https://github.com/Stevepurpose/polynomial-Evaluate
- view live app
Top comments (0)