PolyRoots

Introduction

PolyRoots finds the roots of a polynomial to any chosen accuracy using Laguerre's Method. The coefficients of the polynomial can be real or complex.

PolyRoots uses my own multi-precision engine, fp. PolyRoots is released as freeware, with no restrictive licenses.

Examples

Consider the simple quadratic:

x^2-4x+4

To find its roots enter the coefficients from high to low order, following each coefficient by a Return. You will see:

1
-4
4

Or you can enter the equation as it stands above (or with the terms in any order):

x^2-4x+4 or 4 - 4x + x^2 or -4x+x^2+4 etc.

Accept the "Significant Figures" defaults and click the "Find Roots" button. In "The Roots" you should see:

2 , 0

2 , 0

Polynomial(root):
4.74162503373286e-138 , 0

4.741625033732861e-138 , 0

The listing under "Polynomial(root):" shows the evaluation, using internal precision, of the polynomial for each of the roots. The numbers are a measure of the "goodness" of the roots. They also will approach zero in the limit. If you see evaluations that appear to be too large, you should increase internal accuracy and try again.

Now enter 32 in "Internal:" under "Significant Figures". The calculation will now be done with an internal bit precision of 4 x 32 = 128. The button click should give:

2 , 0

2 , 0

Polynomial(root):
1.175494350822288e-38 , 0

3.526483052466863e-38 , 0

So you see the result of reduced internal bit precision. For some polynomials this may be adequate, but for others you may need a higher internal precision. The default is a bit precision of 4 x 128 = 512.

Consider a polynomial with some complex coefficients:

x^3+(2,3)x^2+(3,-4)x+10

Copy and paste the following into the coefficient text box:

1
2,3
3,-4
10

Or you can copy and paste the polynomial as expressed with x's. Note that for this type of entry complex numbers must be enclosed by parentheses.

Click the Button and note the three distinct complex roots.

Restore "Internal" to 128 and find the roots of:

x^3-1e9x^2+3e9x-2e9

You should have found:

999999997 , 0

2.000000008 , 0

0.999999999 , 0

Polynomial(root):
4.12146990841482e-138 , 0

6.160623452688969e-141 , 0

6.160384070512011e-141 , 0

Now try:

x^10+1

which gives ten values for (-1)^(1/10). You should find:

0.9510565162951536 , 0.3090169943749474

0.9510565162951536 , -0.3090169943749474

0.5877852522924731 , -0.8090169943749474

0.5877852522924731 , 0.8090169943749474

0 , 1

0 , -1

-0.5877852522924731 , -0.8090169943749474

-0.5877852522924731 , 0.8090169943749474

-0.9510565162951536 , -0.3090169943749474

-0.9510565162951536 , 0.3090169943749474

Polynomial(root):
-4.578604275704964e-140 , 3.187655433322432e-139

2.894350148670482e-139 , 1.418705297172973e-139

2.305148881078305e-142 , -7.384488107868683e-142

-1.04191816382113e-163 , 8.682651365176084e-164

1.212479706986824e-139 , 0

1.215329027702094e-139 , 0

1.959530180466196e-139 , -3.476674561055515e-140

-1.394105056132418e-139 , 1.425846544684089e-139

-5.430246832232027e-142 , -7.294882652157342e-142

-6.310735355675061e-142 , -4.474259184470905e-142

Finally, find the roots of the polynomial:

x^7+8.638x^6+31.977876x^5+65.76783164x^4+81.15750424376x^3+60.089016142079904x^2+24.716615306442200512x+4.357186184021382204544

The results should tell you that the above is the polynomial:

(x+1.234)^7

so, for this case, repeated roots gave no problem.

Fractions

Fractions can also be present in the coefficients. They will be evaluated with the current internal precision for the root finding and polynomial evaluation.

Fractions can only be of the form "num/den", because something like "2 1/3" will be interpreted as "21/3", not "7/3" as intended.

With precisions (128, 64) find the roots of

x^2 - x + 2/9

giving

0.6666666666666666666666666666666666666666666666666666666666666667 , 0

0.3333333333333333333333333333333333333333333333333333333333333333 , 0

Polynomial(root):
-7.898445546589549288275726876758703139083089616036050703502550923e-156 , 0

-5.825433698068575502673108357585480421630171313130521950951811037e-157 , 0

So it is evident that the actual roots are 2/3 and 1/3.

Now try this 12th degree polynomial:

1/479001600
-1/3326400
11/604800
-11/18144
11/896
-11/70
77/60
-33/5
165/8
-110/3
33
-12
1

You should only find real roots with the largest being:

37.09912104446692033663891427635811188899333660480199944688519611

Round To Zero

When "Round To Zero" is ON, root values which are very close to zero are set to zero. Usually this is what you want. But for some polynomials you should set "Round To Zero" to OFF. With the setting as ON and precision (128, 16) try

x^2 - 1e100x + 1

which gives

1.e100 , 0)

(0 , 0)

Polynomial(root):
(3.038581678643136e36 , 0)

(1 , 0)

Clearly the second root (0, 0) is incorrect as shown by Polynomial(root) = (1, 0). You might think the first root is also incorrect because of the (3.038581678643136e36 , 0) value. But the real part is about 164 orders of magnitude below the value x^2 = (1e100)^2 = 1e200, so (1.e100 , 0) is a good root.

Now set "Round To Zero" to OFF and click "Find Roots", giving

(1.e100 , 1.310624722422906e-64)

(1.e-100 , 1.41053081692023e-256)

Polynomial(root):
(3.038581678643136e36 , 1.310624722422906e36)

(7.458340731200207e-155 , -1.331998582445268e-156)

So now we have two good roots. To see more accurate roots set precision to (700, 700).

I hope you will enjoy using PolyRoots. But remember that no root finder program is perfect. Some polynomials will defeat PolyRoots.

Dr. Robert M. Delaney
Emeritus Professor of Physics
Saint Louis University
delaneyrm@earthlink.net
delaneyrm@mac.com
delaneyrm@slu.edu