Difference between revisions of "TADM2E 2.5"

Latest revision as of 00:04, 20 June 2017

(a) worst case is $$ 2n $$ multiplications and $$ n $$ additions

(b) In any case the algorithm performs $$ 2n $$ multiplications.

  for i := 1 to n do
      xpower := x * xpower;  --------- (i)
      p := p + ai * xpower     ---------(ii)
  end

Executes exactly $$ n $$ times.
Also executes $$ n $$ times . Even if some ai is $$ 0 $$ , it still performs p := p + 0 * xpower, which of course involves a multiplication with $$ 0 $$ .

So the average number of multiplications is:

$$ = (2*n + 2*n + ....(m-times)...+2*n)/m $$

$$ = 2*n*m/m $$

$$ = 2*n $$

(c) There is a faster algorithm for polynomial evaluation known as Horner's method. It requires $$ n $$ additions and $$ n $$ multiplications:

 res = 0;
 for (i = n; i >= 0; i--) {
     res = (res * x) + aᵢ;
 }
 return res;

@@ Line 22: / Line 22: @@
    res = 0;
-   for (i = n ; i &gt;= 0;i--) {
+   for (i = n; i &gt;= 0; i--) {
        res = (res * x) + aᵢ;
    }