The long-hand method for square rooting real numbers has been mentioned here in a couple of threads.

Is there a way to adapt this method for taking the square roots of polynomials, like you can do with long division and polynomial division? (Basically, it would amount to getting a Laurent series for sqrt(p(x)) where p is a polynomial.)

## Algorithm for polynomial square roots?

**Moderators:** gmalivuk, Moderators General, Prelates

- skeptical scientist
- closed-minded spiritualist
**Posts:**6142**Joined:**Tue Nov 28, 2006 6:09 am UTC**Location:**San Francisco

- skeptical scientist
- closed-minded spiritualist
**Posts:**6142**Joined:**Tue Nov 28, 2006 6:09 am UTC**Location:**San Francisco

Ok, what exactly is it that you want? A procedure that gives the Laurent series (about 0) for the square root of any even degree polynomial? Of course even degree polynomials have Laurent series for sufficiently large annuli, because the x^2n term dominates and has a single-valued square root (2, in fact). On the other hand, if your polynomial has odd degree you won't have a Laurent series for large annuli - your only hope is for small annuli if the other terms let you behave nicely enough somewhere that you have a single-valued square root, which isn't ensured in general.

Anyways, wouldn't any reasonable square root algorithm be analogous to the division algorithm, and therefore calculate higher order terms first and then calculate lower order terms, which would pretty much destroy all hope when you have infinitely many terms with positive degree?

Of course, if you just look in a neighborhood around some point z_0 your polynomial p is nonzero, you can get a perfectly nice Laurent expansion for sqrt(p(z)) - in fact a Taylor series expansion. And since Taylor series are unique, you should just get the Taylor series for sqrt (about p(z_0)) applied to p(z) (i.e. plug in p(z)^n for z^n, expand it out, and regroup terms so you again get a power series). Which means that if p(z) is already a square in C[z], you should get a lot of cancellations of terms in the Taylor series and be left with it's square root (since Taylor series are unique). That's what I meant by substituting it into the series for sqrt(x).

Anyways, wouldn't any reasonable square root algorithm be analogous to the division algorithm, and therefore calculate higher order terms first and then calculate lower order terms, which would pretty much destroy all hope when you have infinitely many terms with positive degree?

Of course, if you just look in a neighborhood around some point z_0 your polynomial p is nonzero, you can get a perfectly nice Laurent expansion for sqrt(p(z)) - in fact a Taylor series expansion. And since Taylor series are unique, you should just get the Taylor series for sqrt (about p(z_0)) applied to p(z) (i.e. plug in p(z)^n for z^n, expand it out, and regroup terms so you again get a power series). Which means that if p(z) is already a square in C[z], you should get a lot of cancellations of terms in the Taylor series and be left with it's square root (since Taylor series are unique). That's what I meant by substituting it into the series for sqrt(x).

I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

"With math, all things are possible." —Rebecca Watson

- bitwiseshiftleft
**Posts:**295**Joined:**Tue Jan 09, 2007 9:07 am UTC**Location:**Stanford-
**Contact:**

### Re: Algorithm for polynomial square roots?

gmalivuk wrote:The long-hand method for square rooting real numbers has been mentioned here in a couple of threads.

Is there a way to adapt this method for taking the square roots of polynomials, like you can do with long division and polynomial division? (Basically, it would amount to getting a Laurent series for sqrt(p(x)) where p is a polynomial.)

Sure. It's a Hensel's lemma type thing, and it's even easier than square-rooting real numbers. (It's the same as the long-hand algorithm, but with no carries.)

For a polynomial P, define P_j to be the j-th coefficient and higher.

Assume that the polynomial P(x) is monic and of even degree 2i, over a field of characteristic other than 2. Now start the square root polynomial Q_i(x) at x^i. Then Q_j = Q_j+1 + (P - ((Q_j+1)^2)_{i+j} / 2 x^i}.

For instance, to compute the square root of P := x^4 + 4x^3 + 6x^2 + 4x + 1, set Q_2 = x^2. Then Q_1 = Q_2 + ((P - x^4) / 2)_3 / 2x^2 = Q_2 + 2x = x^2 + 2x. Q_0 = Q_2 + ((P- (x^4 + 4 x^3 + 4x^2))_2) / 2x = Q_1 + 1 = x^2 + 2x + 1.

In this case, the polynomial is square, so you're done, but if it's not square you can make a Laurent series.

### Who is online

Users browsing this forum: No registered users and 8 guests