Pseudocode and Playing Computer

Horner's algorithm is tricky enough for beginners, it is especially helpful to start with pseudocode. So here is the pseudocode for Horner's algorithm for a polynomial of degree $n$. In this style of pseudocode we enumerate the steps for clarity.

   Step 1: Set p = a[n]
   Step 2: Do step 3 for i from n-1 to 0, decreasing i by 1
        Step 3: set p = a[i] + x0 * p
   Step 4: The value of P(x_0) is p

To check the algorithm we first compare it with the mathematical expression of the answer to be sure it agrees algebraically. Then we "play computer". Here is how. First pick a simple, but not too simple example. Let's try evaluating the example polynomial above at $x = 2$. On a piece of paper write down the values of the coefficients $a_i$ and leave a space for recording the current value of $p$ and $i$ as you go along. Then write down the result of Step 1. You should have $p = 7$. Then start the loop. You should first have $i = 2$. Carry out step 3 and reassign the value of $p$. Then reassign the value of $i$. Repeat until the loop is finished. Your answer should be 70.

You should also check special cases, such as the case $n = 0$. Indeed we get the correct answer $P(x_0) = a_0$, as long as we don't do step 3 when $n-1 < 0$. It will work if we code it with a for loop.

Playing computer should always be your first line of defense in preventing bugs in your code. It is far easier to catch errors at this stage of code development than later after you have compiled and run the real code.