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,-2input == ( + 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,-2input == ( + 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: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?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?Is this the most efficient way to solve this or is there some 3-step process I never did in the math class?
Rational Polynomial Factoring method
java;performance;mathematics
Why return the answer as a String? I would think the answer would be more useful if you:Created a Polynomial data type.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 polynomialLet poq = the rational numbers from your `poq` method.initialize the list of factors to the empty listfor 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 polyDone!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 problemPerhaps 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 <= for to compute the sqrt outside the loop:imax = Math.ceil( Math.sqrt(f) )for (i = 1; i <= imax; i += inc) { ... }multiple rootsThe 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)