How do I factor Polynomials with PHP?

[tristanhall]

Hey guys!
I am working on creating a website that offers resources and calculators for a lot of algebraic and geometric equations. One thing that I want it to do is factor polynomial equations. For example,
x^2-x-2=f(x) would become f(x)=(x+1)(x-2).
WolframAlpha.com does this for all polynomials so I know that it can be done but I don't know if it can be done with PHP. Here's my idea of what to do:
1. Starting with a form: aX^2+bX+c=0
2. The user will be asked to provide an integer for a, b, and c.
3. We create a polynomial equation in PHP using the form input. This will be what the code will check against to make sure it is correct.

$polynomial = $_POST['a'].'x<sup>2</sup>+'.$_POST['b'].'x+'.$_POST['c'];

4. We create 4 arrays:

$a1 = array(); //We will fill this with integers -200 to 200
   $a2 = array(); //Filled with same range
   $b = array(); //Filled with same range
   $c = array(); //Filled with same range

Explanation for arrays: a1 will fill the number in A1 of (A1+B)(A2+C)
5. I now want to have a do {} while setup that goes through all the possible combinations of numbers out of those 4 arrays (putting the numbers in their designated spots) and do the following: Multiply A1*A2. Put that in front of x^2 in the polynomial. Multiply B*A2 and A1*C. Add those values to each other and put it in front of x in the polynomial. Finally multiply C*B and append it to the end.
6. Each time it makes a combination and does the math I want it to check the polynomial created against the polynomial from the initial form we used. It will check after it multiplies that factors that it created.
7. Once it has found a match then it will echo the factors onto the webpage.

Sorry this is SO lengthy. I think this is a pretty good start but I want to know if anyone has any better ideas at improving this. I also apologize for the lack of actual code that's there. I just got this idea recently and haven't been able to put together a test just yet. I'll post anything I come up with. Thanks a million in advance!
Regards,
Tristan

[tristanhall]

Scratch that last idea. It would've taken forever to load the script and it didn't support decimals or numbers larger/less than 200 or -200. Here's an algorithm for finding the roots of the polynomial and then we can use that to create a factored polynomial. I found this at http://en.wikipedia.org/wiki/Root-finding_algorithm

Suppose p(x) = x3+x2−5x+3 is the function whose roots we want to find. We calculate p′(x) = 3x2+2x−5. Now divide p′(x) into p(x) to get p(x) = p′(x)·((1/3)x+(1/9))+((−32/9)x+(32/9)). Divide the remainder by −32/9 to get x−1 which is monic. Divide x−1 into p′(x) to get p′(x) = (x−1)·(3x+5)+0. Since the remainder is zero, g(x) = x−1. So the multiple root of p(x) is r = 1. Dividing p(x) by (x−1)2, we get p(x) = (x+3)(x−1)2 so the other root is −3, a single root.

This would be much easier to implement in PHP and you could use arrays to represent the power of each x variable.
Example: x^2 would be array(x,x)
x^4 would be array(x,x,x,x)
etc.
Let me know if you have any questions. I will be working on a test of this over the weekend.