# Horner’s method
When evaluating a polynomial function (1) in a computer program, the naivest way usually result in more computation complexcity.
In order to speed up the process, Horner's scheme were used.
\begin{equation}
P(x) = a_0 + a_1 x + a_2 x^2 + ... + a_n x^n
\tag{1}
\end{equation}
Rather than direct evaluating (1), Horner's scheme change (1) into (2) which can give the same result but a more efficient way.
Naive way of evaluating polynomail requires at most $n$ additions and $(n^2+n)/2$ multiplications while Horner's scheme only require $n$ additions and $n$ multiplications.
\begin{equation}
P(x) = a_0 + x\left(a_1 + x\left(a_2 + x\left(a_3+...+x\left(a_{n-1}+xa_n\right)\right)\right)\right)
\tag{2}
\end{equation}
Following program first computing the coefficient $a_j$, then I generate a random number using subroutine RANDOM\_NUMBER. Finally, I use another intrinsic function
CPU\_TIME to measure time it takes for two different approach to evaluating the polynomial ($10^5$ times).

## Code

!========================================================
!   Purpose: Camparing Horner's scheme with naive way
!
!   Methods: Horner's Method
!       
!       Date        Programer       Description of change
!       ====        =========       =====================
!     8/13/20        MorrisH        Original Code
!========================================================
PROGRAM MAIN
    IMPLICIT NONE
    REAL(8) :: a(100), start, finish, x
    REAL(8) :: NAIVE, HORNER
    INTEGER :: i,

    CALL RANDOM_SEED()
    CALL RANDOM_NUMBER(x)
    open(99, file='naive.dat', status='unknown')
    open(66, file='horner.dat', status='unknown')

    do i = 1, 100, 2
        a(i) = 1.d0 / DBLE(i)
    end do
    do i = 2, 100, 2
        a(i) = -1.d0 / DBLE(i)
    end do

    CALL CPU_TIME(start)
    do i = 1, 100000
        ans = NAIVE(a, x)
    end do
    CALL CPU_TIME(finish)
    ! print *, ans
    ! print '("Naive method cost : ", f7.5, "seconds")', finish-start
    write(99, *) finish-start, ans


    CALL CPU_TIME(start)
    do i = 1, 100000
        ans = HORNER(a, x)
    end do
    CALL CPU_TIME(finish)
    ! print *, ans
    ! print '("Horner method cost : ", f7.5, "seconds")', finish-start
    write(66, *) finish-start, ans

END PROGRAM MAIN

DOUBLE PRECISION FUNCTION NAIVE(a, x)
    IMPLICIT NONE
    REAL(8) :: a(100), x
    INTEGER :: i

    NAIVE = 0.d0
    do i = 1, 100
        NAIVE = NAIVE + a(i) * x ** DBLE(i)
    end do

END FUNCTION NAIVE

DOUBLE PRECISION FUNCTION HORNER(a, x)
    IMPLICIT NONE
    REAL(8) :: a(100), x
    INTEGER :: i

    HORNER = x * a(100)
    do i = 100, 2, -1
       HORNER = (HORNER + a(i-1)) * x 
    end do

END FUNCTION HORNER

## Result
I calculate the time it takes for both method to preform $10^5$ times, and divide the time it takes using naive method by the time of evaluating using Horner's method. Naive way cost roughly 7 times longer to calculate in this particular example than Horner's method did.


\begin{equation}
P(x) = \dfrac{x}{1} + \dfrac{x^2}{2} + ... + \dfrac{x^n}{n}
= x\left(\dfrac{1}{1}+x\left(\dfrac{1}{2}+x\left(\dfrac{1}{3}+...+x\left(\dfrac{1}{n-1}+x\dfrac{1}{n}\right)\right)\right)\right)
\tag{3}
\end{equation}

For meausering the accuracy, I evaluating (3) from $x=-100$ to $x=100$ using two method. But it seems that the accuracy are roughly the same in this particular example.