How I Built Web App To Evaluate Polynomials Using Horner's Algorithm
Tags: webdev, algorithms, javascript, programming
Published: 2023-09-15 15:54:57

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/t5x5r5v1nwjs7tjemmcw.jpg)

Or

f(x) = a<sub>0</sub> + a<sub>1</sub>x + a<sub>2</sub> x^2 + ... + a <sub>n</sub>   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:
1. Make k = n
2. set b<sub>k</sub>=a<sub>k</sub>
3. b<sub>k-1</sub>=a<sub>k-1</sub> + b<sub>k</sub>x<sub>0</sub>
4. K=k-1
5. If k ≥ 0, go back to step 3
else end.
Where x<sub>0</sub>=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) = a<sub>0</sub> + a<sub>1</sub>x + a<sub>2</sub> x^2 + a<sub>3</sub>x^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:
b<sub>3</sub>=a<sub>3</sub>
a<sub>3</sub>=2
b<sub>3</sub>=2

step 3: 
  b<sub>2</sub>=a<sub>2</sub> + b<sub>3</sub>x<sub>0</sub>
b<sub>2</sub>=4 + (2*3)
b<sub>2</sub>=10

step 4:
k=2-1
k=1

Back to step 3:
b<sub>1</sub>=a<sub>1</sub> + b<sub>2</sub>x<sub>0</sub>
b<sub>1</sub> = 0 + (10*3)
b<sub>1</sub> = 30

step 4:
k=1-1
k=0

Back to step 3:
b<sub>0</sub>=a<sub>0</sub> + b<sub>1</sub>x<sub>0</sub>
b<sub>0</sub> = 3 + (30*3)
b<sub>0</sub> = 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](https://www.math10.com/en/algebra/horner.html#:~:text=Horner's%20rule%20for%20polynomial%20division,multiplication%20and%20one%20addition%20processes.)

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.
1. Input field to take the value of x.
2. Input field to enter co-efficients of x.
3. A button to submit each entry.
4. We need a display where users can read from, we will use an HTML paragraph element for this.
5. 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](https://github.com/Stevepurpose/polynomial-Evaluate), 
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`.

```javascript
let polynomial=[]
```
Some HTML code:

```html
<!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:

```javascript
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 `choices`which 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.

```javascript
/*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.

```javascript
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`

```javascript
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 b<sub>k</sub> = a<sub>k</sub>. 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

https://stevepurpose.github.io/polynomial-Evaluate/