# Rational Polynomial Factoring method

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) {
}
}
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)
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]);
for(int i = 1; i<coeff.length; i++){
if(coeff[i].getNumerator()!=0)
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?

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)

• Nice answer. I though the last point was not needed since the compiler would obviously optimize it away but it turns out that it not the case. Sep 8, 2015 at 16:08
• @Winther that link is from 4 years ago, with java 6, I wouldn't be surprised if it now optimized it, but it probably still can't safely do it. Sep 8, 2015 at 16:14
• Thank you! I call _solve() again because what if the polynomial had a squared factor (i.e. (x-2)^2 * (x^2-5x+3)). The for loop would simply find the factor once and never come back to it. Is there a way to get around that with the for loop? Sep 9, 2015 at 0:00
• Answer updated. Sep 9, 2015 at 0:04
• Thank you! I'll mark it as correct. I have one more question: Have you ever seen code examples or open source projects that perform this same function that I could maybe take a look at? Sep 9, 2015 at 0:07