Mathematical Question?

[azagahl]

I think the fundamental theorem of algebra says any N-degree polynomial (N > 0) can be factored using N roots. Finding them is hard though...

For 3rd/4th degree equations, there are exact algebraic solutions. look at http://mathworld.wolfram.com/ for Quartic Equations or Cubic equations.

Otherwise, I don't think there is a good method in general. For polynomials with degree 5 and above, you can also get exact solutions but they depend on nasty functions and polynomial transformations. Newton's method is easy and fast and is probably the best bet here, however it doesn't work very well for complex roots or coefficients. E.g. for x*x+1 = 0, Newton's method will probably oscillate or diverge stupidly because there is no real root. The above site is a great resource for this stuff. Here is another method, with its own limitations; I think it uses both first and second derivatives: http://mathworld.wolfram.com/HouseholdersMethod.html

There are actually buttloads of these, which shows how hard this problem is: http://mathworld.wolfram.com/Root-FindingAlgorithm.html

For odd-degree equations (e.g. quintic) with real coefficients, they go toward negative infinity on one side, and positive infinity on the other. In this case you can just start far out on both sides and use a binary search to find a zero. This isn't very fast, but is very easy method to implement. If you use this plus the quartic (degree 4) formula you can easily solve any quintic (degree 5) equation. This is because, when you manage to find a root, you can factor (x - root) out of the polynomial (it should divide with no remainder) to reduce its degree by 1.

Hope this helps.

Edited November 9, 2006 by azagahl