TADM2E 2.5 - Revision history

Tangarang: Standardized code formatting.

2017-06-20T00:04:39Z

Standardized code formatting.

Zapstar: Corrected formatting mistakes.

2015-09-13T13:40:48Z

Corrected formatting mistakes.

Algowikiadmin: Recovering wiki

2014-09-11T18:14:11Z

Recovering wiki

New page

(a) worst case is 2n multiplies. this will include n additions

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

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

(i) executes exactly n times.
(ii) also executes n times . Even if some ai = 0, it still performs
p := p + 0 * xpower ,which of course, involves a multiplication with
0.

So the average number of multiplications is :

<math>(2*n + 2*n + ....(m-times)...+2*n)/m</math>
<math>= 2*n*m/m</math>
<math>= 2*n</math>

(c) There is a fast algorithm for polynomial evaulation known as [http://en.wikipedia.org/wiki/Horner's_method Horner's method]. It requires ''n'' additions and ''n'' multiplications:
== <pre>
res = 0;
for (i = n ; i >= 0;i--) {
res = (res * x) + aᵢ;
}
return res;
</pre> ==

Return to [[Algo-analysis-TADM2E]] ...

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

@@ Line 1: / Line 1: @@
-(a) worst case is 2n multiplies. this will include n additions
+(a) worst case is <math>2n</math> multiplications and <math>n</math> additions
-(b) In any case the algorithm performs 2*n multiplications.
+(b) In any case the algorithm performs <math>2n</math> multiplications.
     for i := 1 to n do
@@ Line 8: / Line 8: @@
     end
-(i) executes exactly n times.
+# Executes exactly <math>n</math> times.
-(ii) also executes n times . Even if some ai  =  0, it still performs
+# Also executes <math>n</math> times . Even if some '''ai''' is  <math>0</math>, it still performs '''p := p + 0 * xpower''', which of course involves a multiplication with <math>0</math>.
-So the average number of multiplications is :
+So the average number of multiplications is:
-&lt;math&gt;(2*n + 2*n + ....(m-times)...+2*n)/m&lt;/math&gt;
+<math>= (2*n + 2*n + ....(m-times)...+2*n)/m</math>
-(c) There is a fast algorithm for polynomial evaulation known as [http://en.wikipedia.org/wiki/Horner's_method Horner's method]. It requires ''n'' additions and ''n'' multiplications:
+(c) There is a faster algorithm for polynomial evaluation known as [http://en.wikipedia.org/wiki/Horner's_method Horner's method]. It requires <math>n</math> additions and <math>n</math> multiplications:
-Return to [[Algo-analysis-TADM2E]] ...
+Return to [[Algo-analysis-TADM2E]]