Horner's Method

In this notebook we shall discuss about Horner's method of computing polynomials.
These are the polynomials and the value at which we will be computing these polynomials.

polynomials = [
    ([2, 0, 3, 1], 2),
    ([2, -6, 2, -1], 3),
    ([1, -6, 11, -6], 5),
    ([2,3,-4,1], 10),
]

This is the decorator which will return the time taken by the function to compute the result, along with the result itself

import time as T

def show_time(func):
    def inner(*args, **kwargs):
        start_time = T.time()
        res = func(*args, **kwargs)
        return (res, round((T.time()-start_time)*(10**6),3))
    return inner

Naive Approach

@show_time
def naive_calc(arr, x) -> float:
    r = arr[-1]
    m = 1
    i = -2
    n = -len(arr)
    while i >= n:
        m *= x
        r += m * arr[i]
        i -= 1
    return r

Recursive and Iterative approach of Horner's algorithm

calc = lambda a, b, x: a * x + b

def rec_compute(arr, x, t, index = 1) -> float:
    r = calc(t, arr[index], x)
    if index == len(arr) - 1:
        return r
    return rec_compute(arr, x, r, index + 1)

@show_time
def rec_compute_caller(arr, x):
    return rec_compute(arr, x, arr[0])

@show_time
def loop_compute(arr, x) -> float:
    i = 0
    r = arr[i]
    while i < (len(arr) - 1):
        r = calc(r, arr[i + 1], x)
        i += 1
    return r

Function to get equation from the coefficient array of the polynomial

def updateStringAtIndex(text:str, index:int, char) -> str:
    arr = list(text)
    arr[index] = char
    return ''.join(arr)

def equationFromPol(pol) -> str:
    n = len(pol)
    equation = ""
    for i in pol:
        if i != 0:
            if n == 1:
                if i < 0:
                    equation = updateStringAtIndex(equation,-1,"")
                equation += f"{i}"
            elif n == 2:
                if i == 1: equation += "x"
                elif i== -1:
                    equation = updateStringAtIndex(equation,-1,"-")
                    equation += "x"
                else:
                    if i < 0:
                        equation = updateStringAtIndex(equation,-1,"")
                    equation += f"{i}x+"
            else:
                if i == 1: equation += "x^{%d}+"%(n-1)
                elif i == -1:
                    equation = updateStringAtIndex(equation,-1,"")
                    equation += "x^{%d}+"%(n-1)
                else:
                    if i < 0:
                        equation = updateStringAtIndex(equation,-1,"")
                    equation += "%dx^{%d}+"%(i,n-1)
        n -= 1
    if equation[-1] == "+":
        equation = updateStringAtIndex(equation,-1,"")
    return equation              

Driver code

from IPython.display import HTML, display

results = ""

for pol, value in polynomials:
    results += "<tr>"
    
    eq = equationFromPol(pol)
    res1 = naive_calc(pol, value)
    res2 = rec_compute_caller(pol, value)
    res3 = loop_compute(pol, value)
        
    results += f'''
        <td>${eq}$</td>
        <td>{value}</td>
        <td>{res1[0]}</td>
        <td>{res1[1]}</td>
        <td>{res2[0]}</td>
        <td>{res2[1]}</td>
        <td>{res3[0]}</td>
        <td>{res3[1]}</td>
    </tr>
    '''

display(HTML('''<style>
td {
    color: #111827;
    font-weight: 15px;
    text-align: center;
    border: 1px solid black;
}
th {
    color: #e5f4fb;
    background-color: #1971c2;
    text-align: center;
}
tr:nth-child(2n) td{
    background-color: #9aceeb;
}
tr:nth-child(2n+1) td{
    background-color: #88c0d0;
}
.rendered_html tr,
.rendered_html th,
.rendered_html td {
     text-align: center;
     border: 1px solid black;
     font-size: 2rem;
}
</style>
<table>
<thead>
    <tr>
        <th rowspan=2>$p(x)$</th>
        <th rowspan=2>$x$</th>
        <th colspan=2>Naive Method</th>
        <th colspan=2>Horner's Method<br/>(Recursive)</th>
        <th colspan=2>Horner's Method<br/>(Iterative)</th>
    </tr>
    <tr>
        <th>Result</th>
        <th>Time (in ms)</th>
        <th>Result</th>
        <th>Time (in ms)</th>
        <th>Result</th>
        <th>Time (in ms)</th>
    </tr>
</thead>
''' + results + "<table><hr/>"))

$p(x)$	$x$	Naive Method		Horner's Method (Recursive)		Horner's Method (Iterative)
		Result	Time (in ms)	Result	Time (in ms)	Result	Time (in ms)
$2x^{3}+3x+1$	2	23	5.484	23	8.106	23	3.815
$2x^{3}-6x^{2}+2x-1$	3	5	4.53	5	5.007	5	3.576
$x^{3}-6x^{2}+11x-6$	5	24	2.623	24	2.623	24	2.384
$2x^{3}+3x^{2}-4x+1$	10	2261	3.099	2261	3.338	2261	2.861

---