CS19002 Programming and Data Structures Laboratory Spring 2010, Section 5

Assignment 6

A multi-variate polynomial can be represented by a sum of non-zero terms. We need to store the number of terms, and a list of the non-zero terms. For example, consider the following 4-variate polynomial, where the variables are denoted by a,b,c,d.

   5a2bd3 - 2d5 + abcd + 31

A possible representation of this polynomial is shown below.
Number of terms4
Term 052103
Term 1-20005
Term 211111
Term 3310000

In order to implement this storage of a multi-variate polynomial, we use the following C structure.

   #define NVAR 5
   #define MAX_TERM 1000

   typedef struct {
      int nterm;
      int term[MAX_TERM][1+NVAR];
   } mvpoly;

I supply a function to print a multi-variate polynomial in the above storage format.

   void polyprint ( mvpoly f )
      int i, k;

      for (i=0; i<f.nterm; ++i) {
         if ((i)&&(f.term[i][0]>=0)) printf("+");
         if (f.term[i][0] != 1) printf("%d", f.term[i][0]);
         for (k=1; k<=NVAR; ++k) {
            if (f.term[i][k]) printf("%c",'a'+(char)(k-1));
            if (f.term[i][k]>1) printf("^%d", f.term[i][k]);

Henceforth, we will assume that n is the number of variables.

Part 1: An initialization function

Write a function in order to return the polynomial

   a + b + c + ... (n variables)

The function should have the following prototype:

   mvpoly setpoly ();

Part 2: The product function

Write a function to compute the product of two multi-variate polynomials. Your function should have the following prototype.
   mvpoly polyprod ( mvpoly f, mvpoly g );

Note that when you multiply two multi-variate polynomials, the same product monomial may appear more than once during the monomial-by-monomial product of the input polynomials. It is, therefore, necessary to collect similar terms in the output polynomial. For example, the product of a+b and a+2b should be computed as a2+3ab+2b2 instead of as a2+2ab+ab+2b2.

Part 3: The main() function

Use n = 5 variables a,b,c,d,e. Compute and print the polynomials (a+b+c+d+e)i for i = 1,2,3,4,5.

Sample output

Here is a possible output for n = 3.

   (a+b+c)^1 = a+b+c

   (a+b+c)^2 = a^2+2ab+2ac+b^2+2bc+c^2

   (a+b+c)^3 = a^3+3a^2b+3a^2c+3ab^2+6abc+3ac^2+b^3+3b^2c+3bc^2+c^3

Lab Home Submission Site My Home