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) = a_dx^d + a_d-1x^d-1 + ... + a₁x + a₀ be a polynomial with integer coefficients a_i. Assume that both a_d and a₀ 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₀ 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 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.

• 120x⁴ + 14x³ - 113x² - 10x + 24
• 24x⁶ + 46x⁵ + 33x⁴ + x³ - 18x² - 5x + 3