Assignment 5

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

#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

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.UseHorner's rulefor that, namely, evaluate the polynomial f(X) = a_{n}X^{n}+ a_{n-1}X^{n-1}+ ... + a_{1}X + a_{0}at an integer n as f(n) = (...((a_{n}n + a_{n-1})n + a_{n-2})n + ... + a_{1})n + a_{0}. */ 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

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 : 8But 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

- Evaluate
`f(X)=X`at^{7}-X`n=1,...,7`and demonstrate that for each such n the value`f(n)`is divisible by 7. - Evaluate
`f(X)=X`at^{8}-X^{4}`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}`n = 1,...,10`. (Don't use binomial coefficients.) - Compute the expansions of
`n(X+1)`using polynomial multiplication iteratively for^{n-1}`n = 1,...,10`. (Don't use binomial coefficients.) - Compute the expansions of the derivatives of
`(X+1)`obtained in Part 3 for^{n}`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.

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

- 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]