Kylie Stamey Kylie Stamey - 9 days ago 6
Java Question

Coding Polynomial Division

I'm trying to code the four basic operators for polynomials for a school assignment. I am currently stuck on the division portion. Wikipedia has a mock-up of the pseudo code but I can't really implement it into my code properly. Part of the assignment was also to use a LinkedList so each of my Polynomials is a LinkedList with Term objects containing a coefficient and exponent variable.

Here's what I have so far:

public void dividePolynomials(LinkedList<Term> a, LinkedList<Term> b)
{
LinkedList<Term> q = new LinkedList<Term>;
LinkedList<Term> r = a;

while(!isEmpty(r) && (r.highestDegree() > d.highestDegree()))
{
int co = r.get(0).getCo()/d.get(0).getCo();
int ex = r.get(0).getEx()/d.get(0).getEx();
Term t = new Term();
}
}


I tried to follow the Wikipedia pseudo code but obviously I didn't complete it. Any help would be much appreciated :)

Answer

Following strictly to the pseudo-code, you'll see that takes in two polynomials, and returns a new polynomial. This may not be consistent with your other operators, but is probably the best choice here. So your method header should be more along the lines of

public QRPair dividePolynomials(LinkedList<Term> a, LinkedList<Term> b)

where QRPair is a class consisting of two polynomials; a quotient and a remainder.

The following is a rough translation of the pseudocode.

public LinkedList<Term> deepCopy(LinkedList<Term> p)   {
    //implement this!
}
public QRPair dividePolynomials(LinkedList<Term> a, LinkedList<Term> b) {
    LinkedList<Term> q = "0"    //set q to be the polynomial 0
    LinkedList<Term> r = deepCopy(a);  //want a copy of a, not just reference.      
    while(!isEmpty(r) && (r.highestDegree() > d.highestDegree()))
    {
            int co = r.get(0).getCo()/d.get(0).getCo();
            int ex = r.get(0).getEx()/d.get(0).getEx();
            Term t = new Term(co,ex);
            q = addPolynomials(q,t);
            r = subtractPolynomials(r,multiplyPolynomials(t,d));
            //assume subtract/multiplyPolynomial returns LinkedList<Term>
    }
    return QRPair(q,r);
}

Note that you still have to implement deepCopy. The reason why we can't do the assignment r = a is because that means r and a would reference the same object, which we don't want. Similarly, if we do r = (LinkedList<Term>)a.clone(), then r would have a (shallow) copy of the linked list a. However, each element in r would reference the same object as each element in a, which is also not what we want. We want elements in r to be independent from elements of a.