CS19002 Programming and Data Structures Laboratory |
Spring 2009, Section 2 |

(Structures)

In this assignment, you are supposed to find all the rational roots of a non-constant polynomial with integer coefficients.

Define a rational number as a pair of integers as follows.

typedef struct { int numerator; int denominator; } rational;

Under this representation, an integer *a* can be identified with the rational
number *a*/1. A rational number *a*/*b* is said to be in the reduced
form if gcd(*a*,*b*) = 1. The following functions reduce an arbitrary
rational number to the reduced form.

int gcd ( int a, int b ) { int r; if ((a == 0) && (b == 0)) return 0; if (a < 0) a = -a; if (b < 0) b = -b; while (b) { r = a % b; a = b; b = r; } return a; } rational reduce ( rational x ) { int d; d = gcd(x.numerator,x.denominator); if (d > 0) { x.numerator /= d; x.denominator /= d; } return x; }

A polynomial with integer coefficients can be defined as follows.

typedef struct { int degree; int coefficient[MAX]; } polynomial;

Let *f*(*x*) = *a*_{d}*x*^{d} +
*a*_{d-1}*x*^{d-1} + `...` +
*a*_{1}*x* + *a*_{0} be a polynomial with integer
coefficients *a*_{i}. Assume that both *a*_{d}
and *a*_{0} are non-zero. Then, all the rational roots of *f*(*x*)
are of the form *a*/*b* or -*a*/*b*, where *a* is a positive
integral divisor of *a*_{0} and *b* is a positive integral divisor
of *a*_{d}.

**Part 1 [Credit: 70%]**

Write a function that takes two rational numbers as input and returns their sum in the reduced form.

Write a function that takes two rational numbers as input and returns their product in the reduced form.

Write a functionevalpoly(f,x)that evaluates a polynomialf(x) at a rational valuex.

Write a functionfindroots(f)that accepts a polynomialfas its input parameter and prints all the rational roots of the polynomial. As mentioned above, the roots are of the forma/bor -a/b, whereais searched among the factors of the constant term andbamong the factors of the leading coefficient.

**Part 2 [Credit: 30%]**

Following a naive strategy, as in Part 1, may lead to multiple reporting of same roots, like 1/2 and 2/4. In this part, modify the functionfindroots()so that each root is reported exactly once. Whether you write a new function for Part 2 or update the functionfindroots()of Part 1 is a choice left to you.

Report the output of your program for the following polynomials.

- 120
*x*^{4}+ 14*x*^{3}- 113*x*^{2}- 10*x*+ 24 - 24
*x*^{6}+ 46*x*^{5}+ 33*x*^{4}+*x*^{3}- 18*x*^{2}- 5*x*+ 3