Rational Polynomial Factoring method

Question

I have written a class containing methods to factor a polynomial equation using the p over q method. The method returns a string that is the factored equation.

Here is the class (can also be found here):

public class RPF {

    private RPF(){}

    public static String solve(int... a){
        if(a.length <= 2){
            return "ERROR: 3 or more parameters must be entered.";
        }
        String ans = "";
        int n = a.length;
        List<Integer> fp = (ArrayList<Integer>) factors(Math.abs(a[n-1])); // factors of a0
        List<Integer> fq = (ArrayList<Integer>) factors(Math.abs(a[0]));    // factors of an
        List<Fraction> poq = (ArrayList<Fraction>) getPOverQ(fp, fq);

        Fraction[] fa = new Fraction[a.length];
        for(int i = 0; i<fa.length; i++){
            fa[i] = new Fraction(a[i]);
        }

        ans = _solve(poq, fa);

        return ans;
    }

    private static String _solve(List<Fraction> poq, Fraction[] fa){
        String ans = "";
        boolean solved = false;

        for(Fraction f : poq){
            if(isMonomialFactor(f, fa)){
                ans += "(x "+ (f.isPositive() ? ("- "+f.value()) : ("+ "+f.mult(new Fraction(-1,1)).value())) + ") ";
                fa = polynomialDivision(f, fa).toArray( new Fraction[fa.length-1] );
                solved = true;
                break;
            }
        }
        if(!solved){
            int fac = (int) fa[0].value();
            for(int i = 0; i < fa.length; i++){
                fac = Maths.GCF(fac, (int)fa[i].value());
            }
            if(fac != 1){
                for(int i = 0; i<fa.length; i++){
                    fa[i] = fa[i].divide(new Fraction(fac));
                }
                return ans + fac + _solve(poq, fa);
            }
            ans += "( ";
            for(int i = 0; i<fa.length; i++){
                ans += (fa[i].isPositive() ? ("+ "+fa[i].value()) : ("- "+fa[i].value()*-1))+
                        ((fa.length-i-1 != 0) ? ("x^"+(fa.length-i-1)) : "") + " ";
            }
            ans += " )";
            return ans;
        }
        if(fa.length <= 2){
            int fac = (int) fa[0].value();
            for(int i = 0; i < fa.length; i++){
                fac = Maths.GCF(fac, (int)fa[i].value());
            }
            if(fac != 1){
                ans += fac;
                fa[0] = fa[0].divide(new Fraction(fac));
                fa[1] = fa[1].divide(new Fraction(fac));
            }
            return ans + "("+fa[0].value()+"x + "+fa[1].value()+")";
        }
        return ans + _solve(poq, fa);
    }

    public static List<Integer> factors(int f) {
        int inc = 1;
        if (f % 2 != 0) inc = 2;
        List<Integer> li = new ArrayList<Integer>();
        for (int i = 1; i <= Math.ceil( Math.sqrt(f) ); i=i+inc) {
            if (f % i == 0) {
                li.add(i);
            }
        }
        li.add(f);
        return li;
    }

    public static List<Fraction> getPOverQ(List<Integer> fp, List<Integer> fq){
        List<Fraction> poq = new ArrayList<Fraction>();
        // pos. & neg.
        for(Integer i : fp){
            for(Integer j : fq){
                poq.add( new Fraction(i,j) );
                poq.add( new Fraction(-i,j) );
            }
        }

        return poq;
    }

    public static boolean isMonomialFactor(Fraction f, Fraction[] coeff){       
        Fraction temp = f.mult(coeff[0]);
        for(int i = 1; i<coeff.length; i++){
            if(coeff[i].getNumerator()!=0)
                temp = temp.add(coeff[i]);
            if(i<coeff.length-1) temp = temp.mult(f);
        }
        return temp.equals(Fraction.ZERO);
    }

    public static List<Fraction> polynomialDivision(Fraction f, Fraction[] coeff){
        List<Fraction> rem = new ArrayList<Fraction>();

        Fraction temp = f.mult(coeff[0]);
        rem.add(coeff[0]);
        for(int i = 1; i<coeff.length; i++){
            if(coeff[i].getNumerator()!=0)
                temp = temp.add(coeff[i]);
            rem.add(temp);
            if(i<coeff.length-1) temp = temp.mult(f);
        }
        if(rem.get(rem.size()-1).equals(Fraction.ZERO)){
            rem.remove(rem.size()-1);
        }

        return rem;
    }

}

Some example outputs:

Run #1.
Enter numbers (ex: '1, 3, 4, 2'): 
1,2,1,-2,-2
input == ( + 1x^4 + 2x^3 + 1x^2 - 2x^1 - 2x^0  )
solution == (x - 1.0) (x + 1.0) ( + 1.0x^2 + 2.0x^1 + 2.0  )

Run #2.
Enter numbers (ex: '1, 3, 4, 2'): 
6,-1,4,-1,-2
input == ( + 6x^4 - 1x^3 + 4x^2 - 1x^1 - 2x^0  )
solution == (x + 0.5) (x - 0.6666666666666666) 6( + 1.0x^2 - -0.0x^1 + 1.0  )

Known bugs:

An input coefficient of 0 somewhere in the middle of the polynomial will produce NaN coefficients in the result.

My main concerns and questions:

1. I feel like there is a lot of unnecessary casting between List<Integer> and ArrayList<Integer>. How should I organize them? Should they all be just ArrayList or should I keep the List on the left?
2. I recursively call _solve(). I'm wondering if this is the most efficient way to do things. I assume a loop would be quicker and allow for larger polynomials. Is there a benefit to using recursion here?
3. Is this the most efficient way to solve this or is there some 3-step process I never did in the math class?

Answer 1

Why return the answer as a String? I would think the answer would be more useful if you:

1. Created a Polynomial data type.
2. Returned the answer as a List<Polynomial>

The caller can always convert a List<Polynomial> to a string given a function which converts a single Polynomial to a string.

I think a good candidate for Polynomial would be List<Fraction> (or perhaps ArrayList<Fraction>.) With a small change you can generalize your routine to factor rational polynomials - i.e. not just polynomials with integer coefficients.

why call _solve again?

I'm not sure I understand the point of calling _solve again after the first for loop. My understanding of the p-over-q method is this:

Let poly be a polynomial
Let poq = the rational numbers from your `poq` method.

initialize the list of factors to the empty list
for each rational number r in poq:
  if poly evaluated at r == 0:
    add (x-r) to the list of factors
    let poly = poly / (x-r)
the factorization is:
  the product of the list of factors * the current value of poly
Done!

If none of the rationals in the poq list are roots of the polynomial, then there are no rational factors, and calling _solve again won't change that.

the NaN problem

Perhaps your NaN problem is caused by this code:

  if(fa.length <= 2){
        int fac = (int) fa[0].value();
        for(int i = 0; i < fa.length; i++){
            fac = Maths.GCF(fac, (int)fa[i].value());
        }
        if(fac != 1){
            ans += fac;
            fa[0] = fa[0].divide(new Fraction(fac));
            fa[1] = fa[1].divide(new Fraction(fac));
        }

If fa[i].value is zero for some i, then is it possible that fac will be 0? If so, the result of the division will be a NaN.

However, as I mentioned above, this code is unnecessary, so you can just remove it.

i <= Math.ceil( Math.sqrt(f)

Note that Math.sqrt(f) is computed on each loop iteration. It is better to replace this with the test:

i*i <= f

or to compute the sqrt outside the loop:

imax = Math.ceil( Math.sqrt(f) )
for (i = 1; i <= imax; i += inc) { ... }

multiple roots

The way to deal with multiple roots is to simply change:

if poly evaluated at r == 0:
    add (x-r) to the list of factors
    let poly = poly / (x-r)

to:

while poly evaluated at r == 0:
    add (x-r) to the list of factors
    let poly = poly / (x-r)