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 . 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 0 to n-1, increasing i by 1
Step 3: set p = a[n-1-i] + x * p
Step 4: The value of P(x) 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 . On a piece of paper write down the values of the coefficients and leave a space for recording the current value of and as you go along. Then write down the result of Step 1. You should have . Then start the loop. You should first have . Carry out step 3 and reassign the value of . Then reassign the value of . Repeat until the loop is finished. Your answer should be 70.
You should also check special cases, such as the case . Indeed
we get the correct answer , as long as we don't do step
3 when . It will work if we code it with a
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.