next up previous
Next: Horner's Rule for a Up: Horner's Rule for Polynomials Previous: Pseudocode and Playing Computer

Evaluating a polynomial: poly.cc

Here is the code, translated into C++, and written as a subprogram with a simple main program for reading the polynomial and testing it:

#include <iostream>
#define MAX 50

void poly(int n, double a[], const double x0, double &p){
   int i;
   p = a[n];
   for(i = n - 1; i >= 0; i--){
     p = a[i] + x0*p;
   }
}

int main(){
   int i,n;
   double x0,p;
   double a[MAX+1];

   cout << "Degree of polynomial = ";
   cin >> n;
   if(n > MAX){
      cerr << "Degree must be less than or equal to " << MAX << "\n";
      return 1;
   }
   cout << "Coefficients, a[0], a[1], ..., a[" << n << "]\n";
   for(i = 0; i <= n; i++){
      cin >> a[i];
   }
   cout << "x0 = ";
   cin >> x0;
   poly(n,a,x0,p);
   cout << "P(" << x0 << ") = " << p << "\n";
   return 0;
}

Here are the new features of the code:




   double a[MAX+1];

As we have seen in the previous lesson, this statement declares that a is an array of double precision values of length MAX+1. It reserves space in memory for the array and defines a to be a pointer to the first element a[0]. Notice that we have chosen MAX to be the highest allowed degree of the polynomial. Since a polynomial of degree $n$ takes $n+1$ coefficients, we need MAX+1 spaces.




   for(i = 0; i <= n; i++){
      cin >> a[i];
   }

Note that the limits of the for loop are carefully chosen to read $n+1$ coefficients into a[0] up to a[n].


void poly(int n, double a[], const double x0, double &p){
   ...
}

This is how arguments for singly subscripted arrays can be declared. The empty square brackets signal to the compiler that a is a pointer to a double. It isn't necessary to specify the number of elements, because space for the array is not allocated by the subprogram, but by the calling program (main program in this case). This syntax is equivalent to
void poly(int n, double *a, const double x0, double &p){
   ...
}
but the square bracket notation helps remind us that the pointer is being used to pass an array of numbers.

Doubly subscripted arrays (matrices) can be declared and passed this way:

void func(double b[10][5]){
  ...
}

int main(){
   double b[10][5];
   ...
   func(b);
}

A coding weakness of the main program in the polynomial example above is that it can handle only a fixed maximum degree for the polynomial, since we allocate a fixed amount of storage for a. To evaluate a polynomial of degree 51 requires recompiling with a larger MAX. A better way to do this is to make the declaration depend on the input value n. That declaration can be made only after n is known. Then the only limitation is the maximum available computer memory.

Here is how:

int main(){
   int i,n;
   double x0,p;

   cout << "Degree of polynomial = ";
   cin >> n;
   double a[n+1];
   ...
   return 0;

If the operating system has enough space in memory, the memory allocation succeeds.


next up previous
Next: Horner's Rule for a Up: Horner's Rule for Polynomials Previous: Pseudocode and Playing Computer
Carleton DeTar 2007-08-17