Factoring a multiple-root polynomial

A given multiple-root polynomial is factored into lower-degree distict-root polynomials with natual-order-integer powers. All roots may thus be solved with easy.

The more multiplicities the polynomial roots possess, the more efficient the routine will be. This is contrary to the general public issue.

When coefficients of given polynomial are all integers, then this routine involves only simple arithmetric operations, such as pure integer addition and multiplication, and no floating point compuations in process. The round-off errors may thus be eliminated, if no numerical digital overflow occurs.

The crucial concern is polynomial GCD computation. The classical Euclidean GCD algorithm is employed here, even though it is numerically unstable.

Amazingly, this simple routine gives the exact results for test polynomials of fairly high degrees, such as

p(x) = (x + 1)^50
p(x) = (x^4 - 1)^25
p(x) = (x - 123456789)^4
p(x) = (123x + 456)^4
p(x) = (x^4 -2x^3 +3x^2 -4x +5)^12

Reference:
F C Chang, "Factorization of Multiple-Root Polynomials,"
via fcchang007@yahoo.com