Unit 3.5 Variations on a theme
Some may note that incrementing or decrementing the loop index \(k \) at the end of the loop body is cumbersome since it leads to awkward indexing into the scalars \(a_i \text{.}\) For example, which of the following algorithms would you prefer?
\begin{equation*}
\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}
\hspace{1.0in}
\begin{array}[t]{l}
{\bf Algorithm~5(alt):} \\
y := 0 \\
k := n \\
{\bf while~} k \neq 0 \\
~~~ k := k -1 \\
~~~ y := a_{k} + y \times x \\
{\bf endwhile}
\end{array}
\end{equation*}
The update of \(k \) in the algorithm on the right seems to be more natural. It should be pretty easy to modify the worksheet so that the incrementing or decrementing of \(k \) happens at the top or bottom of the loop body, which then yields alternative correctly derived programs.
Exercise 3.5.
When deriving an algorithm related to \({\bf Invariant~5} \) one could update \(k \) at the top of the loop body:
