Skip to main content

Unit 4.2 A farewell to indices

The fundamental problem with deriving algorithms as we have encountered so far is that bugs in programs are often associated with indices and the quantifiers now used to specify the state of the variables at various points also involves relatively intricate indexing. Thus, the derivation process itself is prone to the introduction of the same kind of bugs that are introduced when programs are developed in a less mathematical fashion. We now show have abstraction comes to the rescue.

From here on, we will use lower case Greek letters for scalars and lower case Roman letters for vectors. With this, the coefficients that define the polynomial can be gathered into a vector

\begin{equation*} a = \left(\begin{array}{c} \alpha_0 \\ \vdots \\ \alpha_{n-1} \end{array} \right) \end{equation*}

and the function that evaluates the polynomial given scalar \(\chi \) (the Greek letter "chi") is given by

\begin{equation*} p( a, \chi ) = \alpha_0 + \alpha_1 \chi + \cdots + \alpha_{n-1} \chi^{n-1}, \end{equation*}

where \(n \) equals the size of the vector \(a \text{,}\)

\begin{equation*} n = m( a ) . \end{equation*}

With this new notation, we wish to compute

\begin{equation*} \psi = p( a, \chi ), \end{equation*}

where we use the Greek lower case letter psi, \(\psi \text{,}\) for what was previously the scalar \(y \text{.}\)

Rather than explicitly indexing to access the elements of a vector \(a \text{,}\) we instead partition into regions:

\begin{equation*} a = \left(\begin{array}{c} \alpha_0 \\ \vdots \\ \alpha_{k-1} \\ \hline \alpha_k \\ \vdots \\ \alpha_{n-1} \end{array} \right) = \left( \begin{array}{c} a_T \\ \hline a_B \end{array} \right), \end{equation*}

where you should read \(a_T \) as "a Top" and \(a_B \) as "a Bottom."

Exercise 4.1.

Show that

\begin{equation*} p( \left( \begin{array}{c} a_T \\ \hline a_B \end{array} \right) , \chi ) = p( a_T, \chi ) + p( a_B, \chi ) \times \chi^{m(a_T )}. \end{equation*}
Solution
\begin{equation*} \begin{array}[t]{l} p( \left( \begin{array}{c} a_T \\ \hline a_B \end{array} \right) , \chi ) \\ ~~~ = ~~~~ \lt \mbox{ definition of } p; k = m( a_T ) \gt \\ \sum_{i=0}^{k-1} \alpha_i \chi^i + \left( \sum_{i=k}^{n-1} \alpha_{i} \chi^i \right) \\ ~~~ = ~~~~ \lt \mbox{ factor out } \chi^k \gt \\ \sum_{i=0}^{k-1} \alpha_i \chi^i + \left( \sum_{i=i}^{n-1-k} \alpha_{i+k} \chi^i \right) \chi^ k \\ ~~~ = ~~~~ \lt \mbox{ definition of } p; k = m( a_T ) \gt \\ p( a_T, \chi ) + p( a_B, \chi ) \times \chi^{m(a_T)} \end{array} \end{equation*}

This last exercise shows how the evaluation of a polynomial \(p( a, \chi ) \) can be recursively defined, meaning in terms of \(p( a_T, \chi ) \) and \(p( a_B, \chi ) \text{.}\)