Algorithm for polynomial square roots?

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26518
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Algorithm for polynomial square roots?

Postby gmalivuk » Sun May 27, 2007 12:18 am UTC

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.)
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

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

Postby skeptical scientist » Sun May 27, 2007 12:31 am UTC

Couldn't you just substitute it in to 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

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26518
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Postby gmalivuk » Sun May 27, 2007 4:11 pm UTC

for what x0 value?

Also, any reasonable polynomial square root algorithm would have to give x+1 for the square root of x^2+2x+1, for instance. An infinite series isn't going to do that.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

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

Postby skeptical scientist » Sun May 27, 2007 8:08 pm UTC

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

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

Re: Algorithm for polynomial square roots?

Postby bitwiseshiftleft » Sun May 27, 2007 10:17 pm UTC

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.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 8 guests