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 fp = (ArrayList) factors(Math.abs(a[n-1])); // factors of a0
List fq = (ArrayList) factors(Math.abs(a[0])); // factors of an
List poq = (ArrayList) getPOverQ(fp, fq);

Fraction[] fa = new Fraction[a.length];
for(int i = 0; i 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 factors(int f) {
int inc = 1;
if (f % 2 != 0) inc = 2;
List li = new ArrayList();
for (int i = 1; i getPOverQ(List fp, List fq){
List poq = new ArrayList();
// 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 polynomialDivision(Fraction f, Fraction[] coeff){
List rem = new ArrayList();

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);

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

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

I think a good candidate for Polynomial would be List (or perhaps ArrayList.) 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)

StackExchange Code Review Q#104075, answer score: 4