CS13002 PDS Lab, Spring 2003, Section 1/A, Assignment 5

CS13002 PDS Lab, Spring 2003, Section 1/A

Assignment 5

[Polynomial arithmetic]

Suppose that we want to handle polynomials of degrees <= 100 and with integer coefficients. We need 101 int cells to store all the coefficients (of X⁰ through X¹⁰⁰) of a polynomial. For enhanced efficiency one needs an additional cell to store the exact degree of a polynomial. The degree of the zero polynomial is conventionally taken to be minus infinity which, in turn, can be conveniently represented by -1. Thus one may define polynomials as follows:

#define MINUS_INFINITY -1    /* Any invalid (negative) degree will do */
#define MAX_DEGREE 100       /* We are interested in polynomials of max degree 100 */
#define POLY_SIZE 102        /* We need 102 int cells, 101 for storing the coefficients, one more for the degree */
#define DEGREE_INDEX 101     /* The degree is stored in the array cell with the highest index */

int f[POLY_SIZE], g[POLY_SIZE], h[POLY_SIZE];   /* f, g and h are to be treated as polynomials */

If the degree of f is d, then f[DEGREE_INDEX] holds the value d, f[i] stores the the coefficient of Xⁱ for i=0,...,d. If d<100, the array locations f[i] for i=d+1,...,100 can hold arbitrary values; you don't need to initialize these to zeros. Since the degree d of a polynomial is stored, there is no need to consult coefficients of Xⁱ for i>d.

Some examples are provided below. Here ? indicates any (uninitialized) value:

Write the following functions to work with our polynomials:

/* Read a polynomial from the terminal. Your routine asks for the degree
   first and then reads the coefficients one by one. */
void polyScan ( int f[] ) ;

/* Print a polynomial to the terminal. Typical examples are:
   0
   -2
   X+1
   -3X+456
   2X^2-34X+5
   X^100+80X^80-60X^60-1
   We recommend you to suppress the zero coefficients and make your
   output look neater. */
void polyPrint ( int f[] ) ;

/* Evaluate a polynomial at a point. You must not use pow.
   Use Horner's rule for that, namely, evaluate the polynomial
   f(X) = a_nXⁿ + a_n-1X^n-1 + ... + a₁X + a₀
   at an integer n as
   f(n) = (...((a_nn + a_n-1)n + a_n-2)n + ... + a₁)n + a₀ . */
int polyEval ( int f[] , int n ) ;   /* Return f(n) */

/* Compare two polynomials. Return 0 if the two polynomials are the same,
   1 otherwise. */
int polyComp ( int f[] , int g[] ) ;

/* Add two polynomials and store the result in a third one. Take care of
   zero polynomials as the operands as well as the result. Also take care
   of the situation that the output polynomial may be the same as one of
   the inputs. Thus calls like polyAdd(h,f,g) will be allowed and so are
   polyAdd(f,f,g) or polyAdd(f,f,f). */
void polyAdd ( int h[] , int f[] , int g[] ) ;  /* Assign f + g to h */

/* Multiply two polynomials. Again take care of zero polynomials and
   repetitions of arguments. */
void polyMul ( int h[] , int f[] , int g[] ) ;  /* Assign f * g to h */

/* Derivative of a polynomial. The output can be the same as the input. */
void polyDerive ( int h[] , int f[] ) ;         /* Assign f' to h */

The following three subroutines may prove to be handy for the working of the above routines. For the convenience of the students we provide implementations of the routines. This also exemplifies how to handle our polynomial data structure.

void polyInit ( int f[] )
{
   f[DEGREE_INDEX] = MINUS_INFINITY;
}

This routine initializes a polynomial to the zero polynomial. The degree is set to minus infinity. That's all!

void polyCompact ( int f[] )
{
   int d, i;

   d = MINUS_INFINITY;
   for (i=f[DEGREE_INDEX]; i>=0; i--) {
      if (f[i] != 0) { d = i; break; }
   }
   f[DEGREE_INDEX] = d;
}

This creates a compact representation of a polynomial. Note that the polynomial X²+3X+8 can also be represented as 0X³+X²+3X+8 or even as 0X¹⁰⁰+0X⁹⁹+...+0X³+X²+3X+8. Thus, for example, a typical session of polyScan could be the following:

Enter degree : 3
Enter coefficient of X^3 : 0
Enter coefficient of X^2 : 1
Enter coefficient of X^1 : 3
Enter coefficient of X^0 : 8

But we don't need the leading zeros which make arithmetic on polynomials inefficient. So one has to adjust the degree after discarding all leading zero coefficients.

The third auxiliary routine is for copying one polynomial to other. It makes a cell-by-cell copy of a polynomial array to another.

void polyCopy ( int h[] , int f[] )   /* Make a copy of f to h */
{
   int i;

   polyCompact(f);   /* optionally make f compact */
   h[DEGREE_INDEX] = f[DEGREE_INDEX];
   for (i=f[DEGREE_INDEX];i>=0;i--) h[i] = f[i];
}

It is very important to note that the call polyCopy(h,f) is different from the assignment h = f. Do not use such assignments of pointers (i.e., arrays) unless you are certain of what you are going to do! An assignment h = f makes h and f point to the same location in the memory. If you modify one, the other also gets modified, i.e., the two arrays cease to be different. (Note: In C++ you can overload the assignment operator by your customized copy routine. Plain C does not provide operator overloading facilities. This is one of the sources of popularity of C++ over C.)

Output

Use the above routines to perform the following tasks:

Evaluate f(X)=X⁷-X at n=1,...,7 and demonstrate that for each such n the value f(n) is divisible by 7.
Evaluate f(X)=X⁸-X⁴ at n=1,...,8 and demonstrate that for each such n the value f(n) is divisible by 8.
Compute the expansions of (X+1)ⁿ using polynomial multiplication iteratively for n = 1,...,10. (Don't use binomial coefficients.)
Compute the expansions of n(X+1)^n-1 using polynomial multiplication iteratively for n = 1,...,10. (Don't use binomial coefficients.)
Compute the expansions of the derivatives of (X+1)ⁿ obtained in Part 3 for n = 1,...,10 and compare the values with those obtained in Part 4.
Verify the product formula (f(X)g(X))' = f'(X)g(X) + f(X)g'(X) for two polynomials f(X) and g(X) of degree 5 read from the terminal.

Sample output

In what follows you will get a guideline of how your output should be presented. Note that Parts 3, 4 and 5 can be clubbed together as shown, that is, run a single loop for n=1,...,10 to do all the tasks assigned in these parts. There is no need to store (X+1)ⁿ and n(X+1)^n-1 for all these values of n and then compare later. Do everything on the fly for a particular n and `forget'.

Evaluating the polynomial f(X) = X^7-X
f(1) = 0, f(1) rem 7 = 0
f(2) = 126, f(2) rem 7 = 0

...

Evaluating the polynomial f(X) = X^8-X^4
f(1) = 0, f(1) rem 8 = 0
f(2) = 240, f(2) rem 8 = 0

...

(X+1)^1 = X+1
((X+1)^1)' = 1
1(X+1)^0 = 1
Comparison result = 0

(X+1)^2 = X^2+2X+1
((X+1)^2)' = 2X+2
2(X+1)^1 = 2X+2
Comparison result = 0

...

Verification of the product formula:
Reading f(X):
Enter degree : 5
Enter coefficient of X^5 : 5
Enter coefficient of X^4 : -4
Enter coefficient of X^3 : 3
Enter coefficient of X^2 : -2
Enter coefficient of X^1 : 1
Enter coefficient of X^0 : 0
Reading g(X):
Enter degree : 5
Enter coefficient of X^5 : -4
Enter coefficient of X^4 : 0
Enter coefficient of X^3 : 0
Enter coefficient of X^2 : 3
Enter coefficient of X^1 : 2
Enter coefficient of X^0 : -1
f(X)                = 5X^5-4X^4+3X^3-2X^2+X
g(X)                = -4X^5+3X^2+2X-1
f(X)g(X)            = -20X^10+16X^9-12X^8+23X^7-6X^6-4X^5+4X^4-4X^3+4X^2-X
(f(X)g(X))'         = -200X^9+144X^8-96X^7+161X^6-36X^5-20X^4+16X^3-12X^2+8X-1
f'(X)g(X)+f(X)g'(X) = -200X^9+144X^8-96X^7+161X^6-36X^5-20X^4+16X^3-12X^2+8X-1
Comparison result = 0

Remarks

Use integer arithmetic only.
You are not allowed to use the math library for this exercise.
Use Horner's rule to evaluate polynomials.
No credits will be given in Parts 3 to 5 if binomial coefficients are used instead of repeated multiplication of polynomials.

If you know what type definitions mean, you can use the following declarations that make your program more legible.

typedef int poly[POLY_SIZE];   /* Create your own data type called poly */

/* Now you can use poly for variable declarations and in function prototypes */
poly f, g, h;
...
void polyCopy ( poly q , poly p ) ;

[Course home] [Home]