# Horner's Method

What is the best way to evaluate 

\\[ f(x) = x^3 + 4x^2 - 10 \\]

at $ x = \dfrac{1}{2} $? The traditional and direct approach is

\\[ f(\dfrac{1}{2}) = \dfrac{1}{2} * \dfrac{1}{2} * \dfrac{1}{2} + 4 * \dfrac{1}{2} * \dfrac{1}{2} - 10 \\]

This procedure takes 4 multiplications and 2 additions where a subtraction can be interpreted as adding a negative number. All together it takes 6 operations to evaluate the function. Is there a way to reduce the number of operations? Rewrite the polynomial in such a way the variable $x$ is factored out:
 
\begin{align}
f(x) & = -10 + 4x^2 + x^3 \\
 & = -10 + x * (0 + 4x + x^2 ) \\
 & = -10 + x * (0 + x * (4 + x))
\end{align}

As you can see, it takes a total of 5 operations to evaluate the function; 3 additions and 2 multiplications. This method is called **Horner's Method**.
The point of this notebook is to check the absolute error and relative error and to test the efficiency of using Horner's Method for numerical computations. In this case, we explore its application to find the root of the equation using Bisection Method.

### Absolute and Relative Error
To calculate the error between the two functions we need to find the absolute and the relative error where $x^*$ is the approximate function and $x$ is the true function.

**Absolute Error** $= |x^* - x| $

**Relative Error** $= \dfrac{|x^* - x|}{|x|} $


```python
def error_analysis(true_fx, approx_fx):
    absolute_error = abs(approx_fx - true_fx)
    relative_error = absolute_error / abs(true_fx)
    return absolute_error, relative_error
```

#### True Function - Naive Method


```python
def f(x):
    return (x ** 3) + (4 * (x ** 2)) - 10
```

#### Approximate Function - Horner's Method


```python
def f_a(x):
    return -10 + 𝑥 * (0 + 𝑥 * (4 + 𝑥))
```

### Bisection Method
Bisection method is a root-finding algorithm based from the intermediate-value theorem from calculus.
You need to verify if a root exist by making sure the two endpoints of the interval $ [a,b] $ or $\{f(a),f(b)\}$ have different signs. If function $ f $ is continuous, then there will be a root $r$ between $a$ and $b$ such that $f(r) = 0$ and $a < r < b$.


```python
import numpy as np
```


```python
def bisection_method(a,b):
    if f(a) * f(b) < 0: 
        roots = []
        while (b - a) / 2 > 1e-7:
            c = (a + b) / 2          
            if f(a) * f(c) < 0:
                b = c
            else:
                a = c
            roots.append(c)
    return np.array(roots)
```


```python
%%timeit
roots = bisection_method(1,2)
```

    24.7 µs ± 1.49 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)



```python
roots = bisection_method(1,2)
```


```python
def bisection_method_hm(a,b):
    if f_a(a) * f_a(b) < 0: 
        roots = []
        while (b - a) / 2 > 1e-7:
            c = (a + b) / 2          
            if f_a(a) * f_a(c) < 0:
                b = c
            else:
                a = c
            roots.append(c)
    return np.array(roots)
```


```python
%%timeit
roots_a = bisection_method_hm(1,2)
```

    20 µs ± 4.59 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)



```python
roots_a = bisection_method(1,2)
```

According to the benchmark an implementation of the Horner's Method perform faster than the naive method. Now let us look at the error analysis to find out whether results are different on a precision level.


```python
absolute_error, relative_error = error_analysis(roots, roots_a)
```


```python
absolute_error
```




    array([0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,
           0., 0., 0., 0., 0., 0.])




```python
relative_error
```




    array([0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,
           0., 0., 0., 0., 0., 0.])



Luckily errors were not found in this example, however polynomials should always be expressed in the nested form before performing an evaluation, because this form minimizes the number of arithmetic calculations, as a result, the errors are reduced. The example \begin{align}
f(x) & = -10 + 4x^2 + x^3 \\
 & = -10 + x * (0 + 4x + x^2 ) \\
 & = -10 + x * (0 + x * (4 + x))
\end{align}

has already placed the coefficients and the variables in the rightful place. Notice we placed an additional coefficient $0$ to fill-in the missing degree.

### Evaluation using Horner's Method

As an engineer we can write an algorithm to evaluate `x` given only the `degree` (or the number of terms in a polynomial) and its `coefficients`. This way we don't have to rewrite a function everytime a new polynomial is introduced.

Consider the following polynomial $ P(x) = a_{k}x^{k} + a_{k-1}x^{k-1} + a_{k-2}x^{k-2} + ... + a_{1}x + a_{0} $ we can evaluate `x` using this algorithm below.


```python
def evaluate(x, k, c, b=None):
    '''
    Evaluate `x` from a polynomial using Horner's Method.

    Parameters
    ----------
    x : int or float
            The value of x
    k : int
            degrees or the number of terms
    c : int or float
            coefficients
    b : int or float
            base points

    Returns
    -------
    y : int or float
            The output of the polynomial
    '''
    y = c[0]
    if b is None:
        for i in range(1, k):
            y = c[i] + (x * y)
    else:
        for i in range(1, k):
            y = (y * (x - b[i])) + c[i]
    return y
```


```python
%%timeit
evaluate(2, 4, [1, 4, 0, -10])
```

    684 ns ± 9.99 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)



```python
%%timeit
f_a(2)
```

    160 ns ± 2.02 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)



```python
%%timeit
f(2)
```

    581 ns ± 9.06 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)


Although Horner's method is slower in comparison with functions whose polynomials are laid out, this method still is efficient as it saves time to rewrite equations and evaluate. We shall look more into the applications of Horner's Method once we get into Interpolation.

### Reference

- R.L. Burden and J.D. Faires. *Numerical Analysis*. Brooks/Cole, Cengage Learning, Boston, 9th edition, 2010.
- Timothy Sauer. 2018. *Numerical Analysis (3rd. ed.)*. Pearson, UK.
- Justin Solomon. 2015. *Numerical Algorithms: Methods for Computer Vision, Machine Learning, and Graphics*. A. K. Peters, Ltd., USA.


```python

```

b74ef0313df3d0fb2ccc823fae18838409234c54
ipynb
Jupyter Notebook
fundamentals/horners_method.ipynb
jrpespinas/numerical-analysis
00fea39c4879893dd60e4a2b7b4dbcb5114234ea
Apache-2.0
2021-01-08T04:17:24.000Z
2021-05-24T16:03:28.000Z
fundamentals/horners_method.ipynb
jrpespinas/numerical-computing
00fea39c4879893dd60e4a2b7b4dbcb5114234ea
Apache-2.0
fundamentals/horners_method.ipynb
jrpespinas/numerical-computing
00fea39c4879893dd60e4a2b7b4dbcb5114234ea
Apache-2.0
Qwen/Qwen-72B
1. YES
2. YES