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{array}{}\text{(1)}& P(x)=a_0+a_{1}x+a_2{x}^2+...+a_n{x}^n\end{array}$$
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{array}{}\text{(2)}& P(x)=a_0+x(a_1+x(a_2+x(a_3+...+x(a_{n-1}+x{a}_n))))\end{array}$$
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{array}{}\text{(3)}& P(x)={\displaystyle \frac{x}{1}}+{\displaystyle \frac{x^2}{2}}+...+{\displaystyle \frac{x^n}{n}}=x({\displaystyle \frac{1}{1}}+x({\displaystyle \frac{1}{2}}+x({\displaystyle \frac{1}{3}}+...+x({\displaystyle \frac{1}{n-1}}+x{\displaystyle \frac{1}{n}}))))\end{array}$$

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.