A simpler multiply and addition polynomial function [closed]

Question

I'm working on a project where I have 2 classes, one class for Monomials and another one for polynomials which are built out of monomials. I would like to make a simpler method for adding and multiplying polynomials, other than my naive method.

public class Monomial {

/**
 * @post this.getCoefficient() == coefficient
 * @post for every v, 'a'<=v<='z', isVariable(v) == false
 */
private int[] exponents=new int[26];
private int ceof;

public Monomial(int coefficient) {

    this.ceof=coefficient;
}

public class Polynomial {

/**
 * Creates a polynomial with (safe copies of) the given monomials
 * 
 * @pre monomials != null
 * @pre for all i, 0 <= i < monmials.length : monomials[i] != null
 * @post for all i, 0 <= i < monmials.length : monomials[i].getCoefficient()
 *       == getMonomial(i).getCoefficient()
 * @post for all i,v, 0 <= i < monmials.length, 'a'<=v<='z' :
 *       monomials[i].getDegree(v) == getMonomial(i).getDegree(v)
 */

private Monomial[] monoms; 

public Polynomial(Monomial[] monomials) {
    this.monoms=monomials;
}

/**
 * @return the number of monomials in this polynomial
 */
public int getMonomialCount() {
    return (this.monoms).length; 
}

/**
 * @pre 0<=index < getMonomialCount()
 * @return a safe copy of the monomial at the given index
 */
public Monomial getMonomial(int index) {
    Monomial copy = this.monoms[index].getCopy();
    return copy;
}

/**
 * @pre other != null
 * @post Creates a new Polynomial which is the sum of this polynomial and
 *       other. E.g., the sum of 13b^2x^3z+15 and -4b^2x^3z is
 *       13b^2x^3z+15-4b^2x^3z
 */
public Polynomial add(Polynomial other) {
    Monomial[] sum=new Monomial[this.monoms.length+other.monoms.length];
    boolean stop=false;
    int maincounter = 0;
    int thiscounter = 0;
    int othercounter = 0;
    while(stop==false){
        if(maincounter<=this.monoms.length-1){
            sum[maincounter]= this.monoms[thiscounter].getCopy();
            thiscounter++;
            maincounter++;
        }
        else{
            sum[maincounter]= other.monoms[othercounter].getCopy();
            othercounter++;
            maincounter++;
        }
        if(maincounter>sum.length-1){
            stop=true;

        }

    }
    return new Polynomial(sum);



}

/**
 * @pre other != null
 * @post Creates a new Polynomial which is the product of this polynomial
 *       and other. E.g., the product of 13b^2x^3z+15 and -4b^2x^3z is
 *       -52b^4x^6z^2-60b^2x^3z
 */
public Polynomial multiply(Polynomial other) {
    int coefficient=0;
    int newDegree=0;
    Monomial newMonomial;
    Monomial thisMonomial;
    Monomial otherMonomial;
    Monomial[] result=new Monomial[this.getMonomialCount()*other.getMonomialCount()];

    for(int i=0;i<this.monoms.length;i++){  
        thisMonomial=this.monoms[i];
        for(int j=0;j<other.monoms.length;j++){
            otherMonomial=other.monoms[j];
            coefficient=thisMonomial.getCoefficient()*otherMonomial.getCoefficient();
            newMonomial=new Monomial(coefficient);
            for(int k=0;k<26;k++){
                if(thisMonomial.isVariable((char)('a'+k))==true&&otherMonomial.isVariable((char)('a'+k))==true){
                newDegree=thisMonomial.getDegree((char)('a'+k))+otherMonomial.getDegree((char)('a'+k));
                }
                else{
                    if(thisMonomial.isVariable((char)('a'+k))==true){
                        newDegree=thisMonomial.getDegree((char)('a'+k));
                    }
                    else{
                        newDegree=otherMonomial.getDegree((char)('a'+k));
                    }
                    }
                newMonomial.setDegree((char)('a'+k),newDegree); 
                }
            result[i]=newMonomial.getCopy();
            }
        }
    Polynomial Polyresult;
    Polyresult=new Polynomial(result);
    return Polyresult;
}

Answer 1

The add method

A loop with an if condition that does one thing for the first n elements and does another thing for the next m elements would be better as two separate for loops for n and m. I suggest to rewrite like that.

The stop variable is pointless. Instead of setting it to false so that while exists, it would have been better to use while (true) and replace stop = true with break. (After you rewrite using two for loops, this variable will naturally disappear.)

Don't write stop == false in conditions, write simply !stop.

Formatting

Your code doesn't follow good formatting practices. It's recommended to put spaces around comparison operators, for example instead of this:

    while(stop==false){
        if(maincounter<=this.monoms.length-1){
            sum[maincounter]= this.monoms[thiscounter].getCopy();
            thiscounter++;
            maincounter++;
        }

Write like this:

    while (stop == false) {
        if (maincounter <= this.monoms.length - 1) {
            sum[maincounter] = this.monoms[thiscounter].getCopy();
            thiscounter++;
            maincounter++;
        }

The indentation and vertical spacing (blank lines) are also a bit odd. Use the auto-reformat feature of your IDE to tidy up your code, for example in Eclipse select all code with Ctrl-A and then Ctrl-Shift-f.

The multiply method

The code as you posted is really hard to read. Here it is nicely reformatted:

public Polynomial multiply(Polynomial other) {
    int coefficient = 0;
    int newDegree = 0;
    Monomial newMonomial;
    Monomial thisMonomial;
    Monomial otherMonomial;
    Monomial[] result = new Monomial[this.getMonomialCount() * other.getMonomialCount()];

    for (int i = 0; i < this.monoms.length; i++) {
        thisMonomial = this.monoms[i];
        for (int j = 0; j < other.monoms.length; j++) {
            otherMonomial = other.monoms[j];
            coefficient = thisMonomial.getCoefficient() * otherMonomial.getCoefficient();
            newMonomial = new Monomial(coefficient);
            for (int k = 0; k < 26; k++) {
                if (thisMonomial.isVariable((char) ('a' + k)) == true
                        && otherMonomial.isVariable((char) ('a' + k)) == true) {
                    newDegree = thisMonomial.getDegree((char) ('a' + k)) + otherMonomial.getDegree((char) ('a' + k));
                } else {
                    if (thisMonomial.isVariable((char) ('a' + k)) == true) {
                        newDegree = thisMonomial.getDegree((char) ('a' + k));
                    } else {
                        newDegree = otherMonomial.getDegree((char) ('a' + k));
                    }
                }
                newMonomial.setDegree((char) ('a' + k), newDegree);
            }
            result[i] = newMonomial.getCopy();
        }
    }
    Polynomial Polyresult;
    Polyresult = new Polynomial(result);
    return Polyresult;
}

Looking from a distance, here's what stands out:

• This piece is used a lot: isVariable((char) ('a' + k)). It would be better to create a local variable char var = (char)('a' + k) early, and avoid repeating the same logic many times
• Don't write conditions like if (cond == true), simplify to if (cond)
• Don't hardcode the number 26, use a constant with a descriptive name instead
• The Polyresult variable at the end doesn't follow recommended naming conventions (camelCase, should have been polyresult), and it's redundant. You could replace the last 3 lines with simply return new Polynomial(result);

Answer 2

The code as given does not compile as getCopy, getCoefficient, getDegree, and isVariable are missing from class Monomial.

Some toString method should also be defined, otherwise debugging is a real pain. You're also missing equals and hashCode.

@post for every v, 'a'<=v<='z', isVariable(v) == false

Should this explain or obfuscate something?

this.ceof=coefficient;

Usually, exactly the same name gets used in constructors and setters. And that's why you need the this qualifier.

Creates a polynomial with (safe copies of) the given monomials

Sometimes, copying may be more (or less) efficient, but generally, immutability is the way to go. With an immutable Monomial you don't have to hunt bugs caused by forgotten calls to getCopy.

public Polynomial(Monomial[] monomials) {
    this.monoms=monomials;
}

What's worse... the code contradicts the comment.

public Monomial getMonomial(int index)

A polynomial is not an indexed array of monomials. Actually, there's no order, so I'd avoid any public methods giving such an access. This may or may not be possible.

public Polynomial add(Polynomial other) {

You should group the monomials here. What you do is representing (x)+(x) as two monomials instead of 2*x.

Monomial[] result=new Monomial[this.getMonomialCount()*other.getMonomialCount()];

This makes it pretty unusable. From something as simple as (x+y)*(x-y) you get x*x - x*y + x*y - y*y instead of x*x - y*y. With every operation, your polynomial grows, never to shrink again.

if(thisMonomial.isVariable((char)('a'+k))==true&&otherMonomial.isVariable((char)('a'+k))==true){
                newDegree=thisMonomial.getDegree((char)('a'+k))+otherMonomial.getDegree((char)('a'+k));
                }
                else{
                    if(thisMonomial.isVariable((char)('a'+k))==true){
                        newDegree=thisMonomial.getDegree((char)('a'+k));
                    }
                    else{
                        newDegree=otherMonomial.getDegree((char)('a'+k));
                    }
                    }

You're needlessly special-casing degree 0, which blows your expression to something terribly complicated... and also broken: In case of both degrees being 0, you simply keep newDegree from the previous iteration as you missed this case. Always minimize the scope. Simply using

char v = (char)('a'+k);
int newDegree = thisMonomial.getDegree(v) + otherMonomial.getDegree(v);

would do.

What I'd suggest?

Create an immutable class UnitMonomial (monomial with coefficient equal 1) with a method multiply(UnitMonomial) and represent Polynomial as Map<UnitMonomial, Integer>. This allows you to simplify the results of all operations.