# Simple and quick way to factor a polynomial

Hello I am looking for a simple and quick way I can enter a polynomial like; ax^3 + bx^2 + cx + d and get an output in the format (l + m)(n+ p)(q + r)

I am unable to find any quick way online

1 Like

Factoring a polynomial and finding the roots of the polynomial are very mathematically close. The polynomial in the question is usually referred to as a cubic polynomial and has a special place in the history of mathematics. A reading of:

will answer most of the question and provide formulas to find the factorization which can be translated into code.

Here is some Julia code to solve a cubic and factor. It demonstrates:

• Taking factored symbolic polynomial and expanding it.
• Extracting the coefficients a,b,c,d.
• Finding roots using PolynomialRoots package
• Assembling a factored form from the root.
• Note there may be issues of numerical accuracy.
``````julia> using PolynomialRoots

julia> using Symbolics

julia> @variables x
1-element Vector{Num}:
x

julia> (2-x)*(5-x)*(7-x)
(7 - x)*(5 - x)*(2 - x)

julia> expand((2-x)*(5-x)*(7-x))
70 - 59x + 14(x^2) - (x^3)

julia> a,b,c,d = -1,14,-59,70
(-1, 14, -59, 70)

julia> roots([d,c,b,a])
3-element Vector{ComplexF64}:
7.0 + 0.0im
5.0 - 0.0im
2.0 + 0.0im

julia> prod(x.-roots([d,c,b,a]))
(-2.0 + x)*(-5.0 + x)*(-7.0 + x)

julia> a*prod(x.-roots([d,c,b,a])) .|> real |> expand
70.0 - 59.0x + 14.0(x^2) - (x^3)
``````

Thanks to nsajko, I’ve learned about AMRVW, and with it:

``````julia> using AMRVW

julia> AMRVW.roots(Float64[d,c,b,a])
3-element Vector{ComplexF64}:
2.0000000000000004 + 0.0im
5.000000000000002 + 0.0im
6.999999999999995 + 0.0im

julia> AMRVW.real_polynomial_roots(Float64[d,c,b,a]).real_roots
3-element Vector{Float64}:
2.0000000000000004
5.000000000000002
6.999999999999995
``````

AMRVW seems to be the better package to go to for finding polynomial roots.

6 Likes

“…enter a polynomial like; ax^3 + bx^2 +cx+d”…

• Are you talking about a cubic polynomial, or
• Is this just an example of a polynomial, where you in reality ask for finding the form “(l+m)(n+p)(q+r)” [whatever that means – presumably you mean (x-x1)(x-x2)(x-x3)??]" of arbitrary order?
2 Likes

For finding polynomial roots numerically, the AMRVW package should be able to give much more accurate results. As of the latest release it also has special support for friendlier handling of real polynomials specifically, in case that helps. The PolynomialRoots package is buggy and not very actively maintained.

2 Likes

If the main focus is finding the roots:

``````import Polynomials as pol

julia> p = pol.Polynomial([1,2,0,3])
Polynomial(1 + 2*x + 3*x^3)

julia> roots(p)
3-element Vector{ComplexF64}:
-0.40231993806281435 + 0.0im
0.20115996903140715 - 0.8877289372825564im
0.20115996903140715 + 0.8877289372825564im
``````

If you want a string expression, you can always do as follows:

``````import Polynomials as pol

julia> p = pol.Polynomial([1,2,0,3])
Polynomial(1 + 2*x + 3*x^3)

julia> p_root = roots(p)
3-element Vector{ComplexF64}:
-0.40231993806281435 + 0.0im
0.20115996903140715 - 0.8877289372825564im
0.20115996903140715 + 0.8877289372825564im

julia> p_string = ""
""

julia> for x0 in p_root
p_string = p_string*"(x - (\$x0))"
end

julia> p_string
"(x - (-0.40231993806281435 + 0.0im))(x - (0.20115996903140715 - 0.8877289372825564im))(x - (0.20115996903140715 + 0.8877289372825564im))"
``````

If you are using `Polynomials.jl`, there is also the `FactoredPolynomial` representation, which might fell more direct:

``````julia> using Polynomials

julia> x = variable()
Polynomial(x)

julia> p = convert(FactoredPolynomial, x^3 - 6x^2 + 11x - 6)
FactoredPolynomial((x - 1.0000000000000002) * (x - 3.0) * (x - 1.9999999999999996))
``````

You might want to round here, as this polynomial should have integer roots:

``````julia> map(x -> round(x, digits=1), p)
FactoredPolynomial((x - 2.0) * (x - 3.0) * (x - 1.0))
``````

As for `AMRVW` or `PolynomialRoots` or just `roots` from `Polynomials`, the faster and more accurate is usually `PolynomialRoots` until the polynomial gets quite large in degree, but the differences are usually quite modest.

2 Likes

Maybe this would be true if the algorithm was implemented correctly (I’m not an expert), but PolynomialRoots seems to suffer from serious bugs, if you take a look at its bug tracker and related threads on this forum.

For genuine symbolic multivariate factorization:

``````julia> using Nemo

julia> R, (x, y, z) = PolynomialRing(ZZ, ["x", "y", "z"]) # declare the list of variables

julia> factor(-3*x^2*y-6*x^2*z-3*x*y^2-5*x*y*z+2*x*z^2+y^2*z+2*y*z^2)
-1 * (x + y) * (y + 2*z) * (3*x - z)
``````
6 Likes

It looks like something has changed:

``````julia> using Nemo

julia> R, (x, y, z) = PolynomialRing(ZZ, ["x", "y", "z"])

ERROR: UndefVarError: `PolynomialRing` not defined
Stacktrace:
[1] top-level scope
@ REPL[2]:1
``````

This is Nemo version 0.45.3.

@greatpet it would be great with an updated example.

It seems like `PolynomialRing` has been renamed to `polynomial_ring`. The following works:

``````julia> using Nemo
julia> R, (x, y, z) = polynomial_ring(ZZ, ["x", "y", "z"]);
julia> factor(-3*x^2*y-6*x^2*z-3*x*y^2-5*x*y*z+2*x*z^2+y^2*z+2*y*z^2)
-1 * (x + y) * (y + 2*z) * (3*x - z)

``````
4 Likes