Exercise 10 (Polynomials) - Deadline June 26th

Generalize the class Polynomial.java and Implement the Euclidean GCD Algorithm

• Generalize the class Polynomial.java from the lecture such that it works with coefficients from an arbitrary field.
  A field is modeled by the following interface: (You can download it from the Moodle page)
  

  public interface CoefficientField<T> {<br>    T add(T val1, T val2);<br>    T multiply(T val1, T val2);<br>    T multiply(T val1, int n);<br>    T invert(T val); // Multiplicative inverse<br>    T negate(T val); // Additive inverse<br>    T unitOne();<br>    T unitZero();<br>}
  

• Implement one representation of a field of your choice. You can approximate the elements by values of an existing java type.
  E.g. You can use Double to represent elements in \(\mathbb R\). (Be careful with Double: In Java 0.0 is different from -0.0.) You can also implement a finite field.
• Implement the euclidean division algorithm for univariate polynomials.
• Implement the euclidean algorithm to compute the GCD of two univariate polynomials over an arbitrary coefficient field and return the unique GCD which has the multiplicative unit element as leading coefficient.
  
• Make the  monomial ordering adjustable.
• Create some polynomials over your implemented field and compute \(p_3=p_1^3*p_2\) where \(p_1\) and \(p_2\) are polynomials for some test cases.
• Compute \(gcd (p_3, p_3')\) and \(gcd (p_3, p_3'')\). What do you observe (write a small pdf or txt file)?
  

Hints

You can extend the class Polynomial in the following way:

    ...
    // Introduce two new instance variables
    private CoefficientField<T> field;
    private Comparator<int[]> monomialOrder;
    ...

The GCD is unique up to the multiplication by a constant. For instance, the GCD of the polynomials \(x^2+ 7x + 6\) and \(x^2 − 5x − 6\) is a polynomial \(C*(x+1)\) where \(C\) is an arbitrary constant.