Algorithm for finding the square root of a polynomial...
Matthew Barrera 
I'm going through Wallace Clarke Boyden's A First Book in Algebra, and there's a section on finding the square root of a perfect square polynomial, eg. $4x^2-12xy+9y^2=(2x-3y)^2$. He describes an algorithm for finding the square root of such a polynomial when it's not immediately apparent, but despite my best efforts, I find the language indecipherable. Can anyone clarify the process he's describing? The example I'm currently wrestling with is $x^6-2x^5+5x^4-6x^3+6x^2-4x+1$.
It's a lot of language to parse, but if anyone wants to take a stab at it, here's the original text:
To find the square root of a polynomial, arrange the terms with reference to the powers of some number; take the square root of the first term of the polynomial for the first term of the root, and subtract its square from the polynomial; divide the first term of the remainder by twice the root found for the next term of the root, and add the quotient to the trial divisor; multiply the complete divisor by the second term of the root, and subtract the product from the remainder. If there is still a remainder, consider the root already found as one term, and proceed as before.
I did some hunting online but didn't turn up anything useful. Is it possible this is an outdated method that's been abandoned for something cleaner?
$\endgroup$ 12 Answers
$\begingroup$It's just saying start with the highest degree and work down. This may not be the fastest but will work or tell you that the thing is not really a square. So, begin with $x^3,$ since the square must be $x^6$ and we get one free choice, $\pm x^3.$ Next, $(x^3 + A x^2)^2 = x^6 + 2 A x^5 + \mbox{more}.$ So $2A = -2, A = -1.$
Alright, $(x^3 -x^2 + B x)^2 = x^6 - 2 x^5 + (2B+1)x^4 + \mbox{more}.$ So $2B+1 = 5$ and $B=2.$
Finally $(x^3 - x^2 + 2 x + C)^2 = x^6 - 2 x^5 + 5 x^4 +(2C -4)x^3 + \mbox{more}.$ So $2C-4 = -6$ and $C=-1.$
Then check $$ (x^3 - x^2 + 2 x -1)^2 = x^6 - 2 x^5 +5 x^4 - 6 x^3 + 6 x^2 - 4 x + 1. $$ So it worked.
$\endgroup$ 3 $\begingroup$If you know that the polynomial is a perfect square, then the square root algorithm works. For example
$$\sqrt{x^6 - 6x^5 + 17x^4 - 36x^3 + 52x^2 - 48x + 36}$$
\begin{array}{lcccccccccccccc} &&x^3 && -3x^2 && +4x && -6\\ &&---&---&---&---&---&---&---\\ x^3 &|& x^6 & -6x^5 & +17x^4 & -36x^3 & +52x^2 & -48x & +36\\ && x^6\\ &&---&---&---\\ &&& -6x^5 & +17x^4 \\ (2)x^3-3x^2 &|& &-6x^5 &+9x^4\\ &&&---&---&---&---\\ &&&& +8x^4 &-36x^3 &+52x^2\\ (2)x^3-(2)3x^2+ 4x &|&&&+8x^4 &-24x^3 &+16x^2\\ &&&&---&---&---&---&---\\ &&&& &-12x^3 &+36x^2 &-48x &+36\\ (2)x^3-(2)3x^2+ (2)4x - 6&|&&&& -12x^3 &+36x^2 &-48x &+36\\ &&&&&---&---&---&---\\ \end{array}
$\text{STEP}\;1.\qquad$ Compute the square root of the leading term (x^6) and put it, (x^3), in the two $\phantom{\text{STEP}\;1.}\qquad$ places shown.
$\text{STEP}\;2.\qquad$ Subtract and bring down the next two terms.
$\text{STEP}\;3.\qquad$ Double the currently displayed quotient $(x^3 \to (2)x^3)$ Then add a new term, $X$, $\phantom{\text{STEP}\;3.}\qquad$ to the quotient such that $X(2x^3 + X)$ will remove the first term, $(-6x^5)$, in the $\phantom{\text{STEP}\;3.}\qquad$ current partial remainder.
$\text{STEP}\;4.\qquad$ Repeat steps $2$ and $3$ until done.
$\endgroup$ 2
