23 Correctness of Horner’s rule
The following code fragment implements Horner’s rule for evaluating a polynomial
$$ \begin {align} P(x) & = \sum _{k = 0}^n a_k x^k \\ & = a_0 + x(a_1 + x(a_2 +· · · + x(a_{n − 1} + xa_n) · · ·)) \end {align} $$
given the coefficients a 0 ; a 1 ; : : : ; a n and a value for x:
1. Asymptotic Running Time
From the pseudocode of Horner’s Rule, the algorithm runs in a loop for all the elements, i.e. it runs atΘ(n) time.
2. Comparison with Naive Algorithm
Pseudocode forA is the array of length n+1 consisting of the coefficients a0,a1,...,an .
The above algorithm runs with for inside another for loopj multiplications to evaluate ajxj and $(n  1)$ additions in total to evaluate a polynomial. Hence, it does ∑nj=0j=n(n+1)/2 multiplications and (n−1) additions. Therefore, the algorithm runs at Θ(n2)
time.
This algorithm is obviously worse than Horner’s rule which runs at linear time.
3. Loop Invariant for the While Loop
Initialization: At the start of the first iteration, we havei=n . So,
y=∑k=0n−(i+1)ak+i+1xk=∑k=0n−(n+1)ak+n+1xk=∑k=0−1ak+n+1xk=0
As the sum is zero, the loop invariant holds after the first loop.
Maintenance: From the loop invariant, for any arbitrary0<=i<n
, at the start of thei th iteration of the while loop of lines 3–5, y=∑n−(i+1)k=0ak+i+1xk
Now, after thei th iteration,
y′=ai+x⋅y=ai+x⋅∑k=0n−(i+1)ak+i+1xk=aix0+∑k=0n−(i+1)ak+i+1xk+1=∑k=−1n−(i+1)ak+i+1xk+1=∑k′=0n−(i+1)ak′+ixk′=∑k′=0n−(i′+1)ak′+i′+1xk′
So, the loop invariant also holds after the loop.
We make two assumption:
i=−1 . So,
y=∑k=0n−(i+1)ak+i+1xk=∑k=0n−(−1+1)ak−1+1xk=∑k=0nakxk
This is precisely what we wanted to calculate.
4. Correctness Argument
When Horner’s rule terminates it successfully evaluates the polynomial as it intended to. This means the algorithm is correct.
The following code fragment implements Horner’s rule for evaluating a polynomial
$$ \begin {align} P(x) & = \sum _{k = 0}^n a_k x^k \\ & = a_0 + x(a_1 + x(a_2 +· · · + x(a_{n − 1} + xa_n) · · ·)) \end {align} $$
given the coefficients a 0 ; a 1 ; : : : ; a n and a value for x:
y = 0 for i = n downto 0 y = a_i + x * y
 In terms of Θnotation, what is the asymptotic running time of this code fragment for Horner’s rule?
 Write pseudocode to implement the naive polynomialevaluation algorithm that computes each term of the polynomial from scratch. What is the running time of this algorithm? How does it compare to Horner’s rule?
 Consider the following loop invariant:.
At the start of each iteration of the for loop of lines 23,
y=∑n−(i+1)k=0ak+i+1xk Interpret a summation with no terms as equaling 0. Your proof should follow the structure of the loop invariant proof presented in this chapter and should show that, at termination,y=∑nk=0akxk .  Conclude by arguing that the given code fragment correctly evaluates a polynomial characterized by the coefficients
a0,a1,...,an .
1. Asymptotic Running Time
From the pseudocode of Horner’s Rule, the algorithm runs in a loop for all the elements, i.e. it runs at
2. Comparison with Naive Algorithm
Pseudocode for
NAIVEPOLYEVAL(A, x)
, where y = 0 for i = 1 to A.length m = 1 for j = 1 to i  1 m = m * x y = y + A[i] * m
The above algorithm runs with for inside another for loop
time.
This algorithm is obviously worse than Horner’s rule which runs at linear time.
3. Loop Invariant for the While Loop
Initialization: At the start of the first iteration, we have
Maintenance: From the loop invariant, for any arbitrary
, at the start of the
Now, after the
We make two assumption:

k′=k+1 : This is valid ask is nothing but the summation parameter. i′=i−1 : This holds as this is precisely the operation done in line 5.
4. Correctness Argument
When Horner’s rule terminates it successfully evaluates the polynomial as it intended to. This means the algorithm is correct.
No comments :
Post a Comment