Skip to main content

Unit 4.6 Translating into code

We have now derived a correct and efficient algorithm for evaluating a polynomial that employs Horner's rule:

In translating this algorithm into code, programming errors can still be introduced. For this reason, we developed an Application Programming Interface (API), the FLAME@lab API [2], that allows the code to closely reflect the algorithm. Here is a function coded with Matlab's scripting language (also used by Octave, an open source tool like Matlab), to which we added a few functions that implement the peculiar way in which indexing is hidden in the FLAME notation:

\(a \rightarrow \left( \begin{array}{c} a_T \\ \hline a_B \end{array} \right) \text{,}\)
where \(a_B \) has \(0 \) elements

[ aT, ... 
  aB ] = FLA_Part_2x1( a, ... 
                       0, 'FLA_BOTTOM' );


\(\left( \begin{array}{c} a_T \\ \hline a_B \end{array} \right) \rightarrow \left( \begin{array}{c} a_0 \\ \alpha_1 \\ \hline a_2 \end{array} \right) \)

[ a0, ... 
  alpha1, ... 
  a2 ] = FLA_Repart_2x1_to_3x1( aT, ... 
                                aB, ... 
                                1, 'FLA_TOP' );


\(\left( \begin{array}{c} a_T \\ \hline a_B \end{array} \right) \leftarrow \left( \begin{array}{c} a_0 \\ \hline \alpha_1 \\ a_2 \end{array} \right) \)

[ aT, ...
  aB ] = FLA_Cont_with_3x1_to_2x1( a0, ...
                                   alpha1, ...
                                   a2, ...
                                   'FLA_BOTTOM' );

For the interested reader, these routines, which hide the details of indexing, are implemented in Octave (or Matlab) as follows:

With this, we hope the following code is self-explanatory:

The points is that with this kind of API, which can be instantiated for different programming languages, the algorithm is translated into code so that the correctness of the algorithm implies the correctness of the implementation.

We can double check whether the polyeval function gives the correct answer by testing it with a representative input. First, evaluate the code cells given above by clicking on "Evaluate (Octave)."

Note that Octave and Matlab start indexing at one: a(1) = 1 , a(2) = 2 , etc.

Of course, since we derived the function to be correct, there is no need to check it by trying a few examples...

“Testing shows the presence, not the absence of bugs” — Dijkstra (1968)

“If you want more effective programmers, you will discover that they should not waste their time debugging, they should not introduce the bugs to start with.” — Dijkstra (1972) The Humble Programmer [3]