CS19002 Programming and Data Structures Laboratory Spring 2009, Section 2

Assignment 7(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) = adxd + ad-1xd-1 + ... + a1x + a0 be a polynomial with integer coefficients ai. Assume that both ad and a0 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 a0 and b is a positive integral divisor of ad.

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 function evalpoly(f,x) that evaluates a polynomial f(x) at a rational value x.
Write a function findroots(f) that accepts a polynomial f as its input parameter and prints all the rational roots of the polynomial. As mentioned above, the roots are of the form a/b or -a/b, where a is searched among the factors of the constant term and b among 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 function findroots() so that each root is reported exactly once. Whether you write a new function for Part 2 or update the function findroots() of Part 1 is a choice left to you.

Report the output of your program for the following polynomials.

• 120x4 + 14x3 - 113x2 - 10x + 24
• 24x6 + 46x5 + 33x4 + x3 - 18x2 - 5x + 3

Submission site | Lab home | Course home | My home