Unit 2.1 Algorithms for evaluating a polynomial
What we noticed in Unit 1.1 is that the conversion from a number written in base \(x \) to a decimal number is accomplished by the formula
\begin{equation*}
a_0 + a_1 \times x + a_2 \times x^2 + \cdots + a_{n-1}
\times x^{n-1}.
\end{equation*}
What this shows is that the evaluation of a polynomial might be an operation of interest. We now use it to discuss how to develop algoriithms and programs.
Exercise 2.1.
Consider
\begin{equation*}
y := a_0 + a_1 x + a_2 x^2,
\end{equation*}
where \(a_0 = 2 \text{,}\) \(a_1 = -1 \text{,}\) \(a_2 = -2 \text{,}\) and \(x = -1 \text{.}\) Execute each of the following algorithms for \(n = 3 \text{:}\)
\begin{equation*}
\begin{array}[t]{l}
{\bf Algorithm~1:} \\
y := 0 \\
k := 0 \\
{\bf while~} k \neq n \\
~~~ y := y + a_{k} \times x^k \\
~~~ k := k + 1 \\
{\bf endwhile}
\end{array}
\hspace{1.0in}
\begin{array}[t]{l}
{\bf Algorithm~5:} \\
y := 0 \\
k := n \\
{\bf while~} k \neq 0 \\
~~~ y := a_{k-1} + y \times x \\
~~~ k := k -1 \\
{\bf endwhile}
\end{array}
\end{equation*}
Here, we present algorithms in a pseudo code that we hope is self-explanatory.
The content of variable \(y \) at different stages of the execution is given by:
\begin{equation*}
\begin{array}{| l | r | r |} \hline
\amp
{\bf Algorithm~1}
\amp
{\bf Algorithm~5}
\\ \hline
{\rm Before~\bf while}
\amp
0
\amp
0
\\ \hline
\mbox{After iteration 1}
\amp
\phantom{(0) + (\phantom{-}2)\times (-1)^0 = 2 }
\amp
\phantom{(-2)+(\phantom{-}0) \times (-1) = -2 }
\\ \hline
\mbox{After iteration 2}
\amp
\phantom{(2) + (-1)\times (-1)^1 = 3}
\amp
\phantom{(-1)+(-2) \times (-1) = \phantom{-}1}
\\ \hline
\mbox{After iteration 3}
\amp
\phantom{(3) + (-2) \times (-1)^2 = 1}
\amp
\phantom{(\phantom{-}2)+(\phantom{-}1) \times (-1) =
\phantom{-}1}
\\ \hline
\mbox{Final result}
\amp
\phantom{1}
\amp
\phantom{1}
\\ \hline
\end{array}
\end{equation*}
Solution
The content of variable \(y \) at different stages of the execution is given by:
\begin{equation*}
\begin{array}{| l | r | r |} \hline
\amp
{\bf Algorithm~1}
\amp
{\bf Algorithm~5}
\\ \hline
{\rm Before~\bf while}
\amp
\color{red} 0
\amp
\color{red} 0
\\ \hline
\mbox{After iteration 1}
\amp
({\color{red} 0}) + (\phantom{-}2)\times (-1)^0 =
\color{red} 2
\amp
(-2)+(\phantom{-}{ \color{red} 0}) \times (-1) =
\color{red} -2
\\ \hline
\mbox{After iteration 2}
\amp
({\color{red} 2}) + (-1)\times (-1)^1 = {\color{red} 3}
\amp
(-1)+({\color{red} -2}) \times (-1) =
\phantom{-}{\color{red} 1}
\\ \hline
\mbox{After iteration 3}
\amp
({\color{red} 3}) + (-2) \times (-1)^2 = 1
\amp
(\phantom{-}2)+(\phantom{-}{\color{red} 1}) \times (-1) =
\phantom{-}1
\\ \hline
\mbox{Final result}
\amp
1
\amp
1
\\ \hline
\end{array}
\end{equation*}
Exercise 2.2.
Consider evaluating
\begin{equation*}
y := a_0 + a_1 x + a_2 x^2 + \cdots + a_{n-1} x^{n-1}.
\end{equation*}
for given integer \(n \ge 0 \text{,}\) and scalars \(a_0, \ldots, a_{n-1} \) and \(x \text{.}\) Which of the following algorithm would you prefer to implement? Why?
\begin{equation*}
\begin{array}[t]{l}
{\bf Algorithm~1:} \\
y := 0 \\
k := 0 \\
{\bf while~} k \neq n \\
~~~ y := y + a_{k} \times x^k \\
~~~ k := k + 1 \\
{\bf endwhile}
\end{array}
\hspace{1.0in}
\begin{array}[t]{l}
{\bf Algorithm~5:} \\
y := 0 \\
k := n \\
{\bf while~} k \neq 0 \\
~~~ y := a_{k-1} + y \times x \\
~~~ k := k -1 \\
{\bf endwhile}
\end{array}
\end{equation*}
HintConsider factors like correctness and number of operations performed in updating \(y \text{.}\)
