# 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?

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

• Looks promising but I am having trouble figuring out your verbs. Step 1: "divide" what from what? Step 2: Subtract what from what? – Ben Farmer Jul 10 '18 at 10:42
• @BenFarmer It's an adaptation of the square root algorithm. – steven gregory Jul 10 '18 at 11:04