# Algorithm for finding the square root of a polynomial…

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?

-
+1 -- that passage is completely opaque. – 6005 Jul 6 at 16:51

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.

-
Nice, thanks. I take it the $2A$, $2B+1$, $2C-4$ are the polynomial coefficients, like something akin to the binomial coefficients (but more terms, obviously)? – ivan Mar 8 '13 at 5:31
@ivan, I deliberately solved one at a time for $A,B,C.$ If I were to take $(x^3 + A x^2 + B x + C )^2$ I would get mixtures of the letters $A,B,C$ in the outcome. My way it is not necessary to worry about those mixtures. – Will Jagy Mar 8 '13 at 5:35
Oh cool! I actually get it now :) – ivan Mar 8 '13 at 5:52

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 divide as 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.

-