[wp34s] Poly root finders?

[emece67]

Hi all,

I'm having trouble with the polyroot program in the wp34s library. I've have tried various versions of it I have found around. But, in my tests (very basic ones), all of them suffer from different issues (machine resets, infinite results, bad roots...).

I've searched the forum about this and have found some discussion about it some years ago. The last version of the wp34s polynomial root solver seems to be this, but if fails, in my case with polinomial $$z^2+1=0$$ giving a double root at z = 0, which is obviously wrong.

I'm not sure if I'm doing something wrong so, does anybody know of a working poly solver for the wp34s? If anybody insists me on the existing solver, I will give it a new try, but perhaps I'll need advice on how to use it.

EDIT: last summer I worked on a Laguerre's method based solver for the wp34s. It is far from being completed (not even functional), so I do not expect it to be usable in the foreseeable future, thus turned to the wp34s library one.

[BarryMead]

(12-03-2015 06:22 PM)emece67 Wrote:  in my case with polinomial $$z^2+1=0$$ giving a double root at z = 0, which is obviously wrong.

The REAL component of both roots IS ZERO. Either you are not reading the answers correctly, or the root solver you picked isn't handling complex answers very well.
Since this particular equation is only of degree 2 you could always solve it with the SLVQ funciton. Put 1 in Z, 0 in Y and 1 in X Representing the a, b and c coefficients of the quadratic equation, and press X.FCN SLVQ.

Immediately after the SLVQ step, the first answer appears in the display. (0 + i1)
When the answer is complex, the manual says the second answer is the complex conjugate of the first, so press CPX X.FCN CONJ then the second answer (0 - i1) appears in the display.

The roots of this equation are (0 + i1) and (0 - i1)

I hope this was helpful, Barry

[Thomas Klemm]

If you only want to calculate roots of real polynomials you could use Bairstow's method. The algorithm finds the roots in complex conjugate pairs using only real arithmetic.

It should be straight forward to translate this program for the HP-11C to the WP-34S. However the trick using L.R. to solve the linear equation probably doesn't work. You could use Cramer's rule instead.

But then of course it doesn't help to solve: \(z^2+1=0\)

Kind regards
Thomas

[fhub]

(12-03-2015 06:22 PM)emece67 Wrote:  ... does anybody know of a working poly solver for the wp34s?

Yes, I do.

More than 3 years ago (while the WP34s was still under development) I've written a polynomial rootsolver (in fact even several versions, first with Bairstow method, then switching to the better Laguerre method).

The final version 'PRS' is a quite long program (520 steps), and it was available in the 'HP Articles Forum' for some time, but I've removed it again from there because of ... (well, I don't want to dredge up this problem).

The program is quite sophisticated, it works for polynomials with degrees upto 39 (but only with real coefficients) -
if you're interested I could upload it again.

Franz

[Dieter]

(12-03-2015 06:22 PM)emece67 Wrote:  I've searched the forum about this and have found some discussion about it some years ago. The last version of the wp34s polynomial root solver seems to be this,

No, that's not the last version. It lacks several changes and 34s modifications that were introduced later. The final version (AFAIK) is found in the library folder of the 34s package, and it's called polyroot.wp34s.

(12-03-2015 06:22 PM)emece67 Wrote:  but if fails, in my case with polinomial $$z^2+1=0$$ giving a double root at z = 0, which is obviously wrong.

As far as I remember the program seemed to work fine. Maybe there is an error in the code you entered?

Dieter

[fhub]

(12-04-2015 11:50 AM)Dieter Wrote:  No, that's not the last version. It lacks several changes and 34s modifications that were introduced later. The final version (AFAIK) is found in the library folder of the 34s package, and it's called polyroot.wp34s.

Well, in fact it is exactly the opposite:
The listing in the WP34s library is from 8.4.2012, wheras the program in the HP-forum article has been updated on 30.8.2013.

Franz

[Dieter]

(12-04-2015 12:04 PM)fhub Wrote:  Well, in fact it is exactly the opposite:
The listing in the WP34s library is from 8.4.2012, wheras the program in the HP-forum article has been updated on 30.8.2013.

The date does not tell the whole story. ;-)

Take a look at the code. The one in the articles forum does not include several obvious improvements, e.g. using RCL arithmetics, replacing EEX CHS 3 ENTER 2 x with a simple 2 SDR 003 and several other changes that have been discussed back then. Maybe the only update was a slight edit to make it run with v3.2 ?

BTW the polyroot.wp34s version I got is dated 12.12.2012, i.e. eight months later than yours.
However, both versions should return correct results, at least for such a simple case. I still assume something has been entered incorrectly.

Dieter

[fhub]

(12-04-2015 12:32 PM)Dieter Wrote:  BTW the polyroot.wp34s version I got is dated 12.12.2012, i.e. eight months later than yours.

Yes, that's the one from the last official 'wp34s_V3.zip' package, but it's still the same as in the Sourceforge 'trunc' folder (dated 8 months earlier).

Anyway, my PRS is much better (but only for real coefficients) ...

Franz

[emece67]

(12-03-2015 10:04 PM)BarryMead Wrote:  The REAL component of both roots IS ZERO. Either you are not reading the answers correctly, or the root solver you picked isn't handling complex answers very well.
Since this particular equation is only of degree 2 you could always solve it with the SLVQ funciton. Put 1 in Z, 0 in Y and 1 in X Representing the a, b and c coefficients of the quadratic equation, and press X.FCN SLVQ.

[...]

Immediately after the SLVQ step, the first answer appears in the display. (0 + i1)
When the answer is complex, the manual says the second answer is the complex conjugate of the first, so press CPX X.FCN CONJ then the second answer (0 - i1) appears in the display.

Thanks Barry. I've just double checked it. Polyroot.wp34s reports both roots to be real and, thus, reports their imaginary parts as zero (as their real parts).

I know about SLVQ, but I was looking for a poly solver I can trust in everyday use.

(12-04-2015 09:34 AM)fhub Wrote:  The final version 'PRS' is a quite long program (520 steps), and it was available in the 'HP Articles Forum' for some time

[...]

The program is quite sophisticated, it works for polynomials with degrees upto 39 (but only with real coefficients) -
if you're interested I could upload it again.

I've read about this program but was unable to find it. Of course I'm interested on it, so I'll thank you if you upload it again. In fact, I turned to the Laguerre's method 'cause I read about your program.

(12-04-2015 11:50 AM)Dieter Wrote:  No, that's not the last version. It lacks several changes and 34s modifications that were introduced later. The final version (AFAIK) is found in the library folder of the 34s package, and it's called polyroot.wp34s.

[...]

As far as I remember the program seemed to work fine. Maybe there is an error in the code you entered?

I have just downloaded the last SVN version of polyroot.wp34s, compiled and tested it with 4 different polynomials of the 2nd & 3rd degree (all with real coeffs). In all cases the program crashed with a -∞ Error. These tests were run in the Qt simulator.

I have not keyed-in the program, just used copy/paste (for the version in the articles forum) or replaced an old file with a new one (for the SVN version).

Still searching...

[fhub]

(12-04-2015 12:58 PM)emece67 Wrote:  I've read about this program but was unable to find it. Of course I'm interested on it, so I'll thank you if you upload it again.

Ok, it's in the attachment.

I've included a 'Readme.txt' (just the former description from the Articles section), but instructions are also in the sourcefile 'PRS.wp34s' at the beginning.

And I've also included a ready-to-use 'wp34s.dat' in case someone doesn't have (or doesn't know how to use) the WP34s compiler - you can just put this file into your WP34s (emulator) folder, then the program is automatically in the RAM.
(if you have already other programs in your RAM, don't forget to make a backup of your old 'wp34s.dat' before).

Franz

[emece67]

(12-04-2015 01:07 PM)fhub Wrote:  Ok, it's in the attachment.

[...]

Downloaded, compiled, tested & working!!

It's even more than I expected, includes root polishing and a mechanism (I'm now studying it) to manage multiple roots .

Superb work! Thanks a lot.

[fhub]

(12-04-2015 01:23 PM)emece67 Wrote:  It's even more than I expected, includes root polishing and a mechanism (I'm now studying it) to manage multiple roots .

Yes, that's what makes the program so big - without these features it would only require about 350 steps.
But without the special routines to handle multiple roots it would fail miserably for such multiple roots (as almost every other polynomial rootsolver does).

Franz

[emece67]

I've been tinkering with this PRS solver for a while. It definitely works quite nicely and even outperforms some other "multiple-root aware" solvers I've tested in Matlab.

After studying the code, now I feel confident enough to understand the way it works and even to modify it to better suit my needs (mainly, accepting complex coeffs). Well, I think I understand it except for the very last lines.

Code:


511 SCI 09
512 ROUND
513 STO Y
514 x[<->] L
515 ALL 00
516 ROUND
517 x=? Y        // round 10-digits=12-digits?
518 STO Z        // round x to 'rational' number
519 [cmplx]DROP

What are they for?

[fhub]

(12-07-2015 05:40 PM)emece67 Wrote:  Well, I think I understand it except for the very last lines.
...
What are they for?

OMG, do you really expect that I remember this after almost 4 years?

Well, after a quick look at the code I think it was about getting 'prettier' results (in some cases).
Assume that any root of the polynomial is exactly 2.345, but since this is an approximate method it may finish with a value of 2.34499999.....99978 (with the used eps=1e-15 the inaccuracy should happen around digit 15 internally).
Now I round this value to 12 digits and to 10 digits, and if these rounded values (in this case both would be 2.345000...) are identical, I just use this rounded value instead of the 15-digit approximation.

[Edit:] Many testsuites for polynomial rootsolvers even use examples with integer roots, e.g. (x-2)^10 or (x-1)*(x-2)*(x-3)*... etc., and with my rounding routine I get indeed exact results.

Franz

[walter b]

Why do you round to 12 and to 10 digits for an error in the 15th digit? Why not round to 13 digits and 12 digits and test for identity? What do I miss?

d:-?

[emece67]

I suspected that the target of this code was related to "beautify" the solutions. What confused me was the 10/12 limits and using SCI with one limit and ALL with the other.

But Franz's explanations gave me enough clues to, if not perfectly undertand the code, at least try to replicate it with my own constructions.

Thanks again & regards.

[fhub]

(12-07-2015 09:59 PM)emece67 Wrote:  What confused me was the 10/12 limits and using SCI with one limit and ALL with the other.

Well, I've worked quite long on this program and you can be sure that I did it exactly this way for good reason, but don't ask me 4 years later 'why' -
I just don't remember.
And today I'm using the WP34s much less than at that time, so I've already forgotten again lots of the 'special features' of this great calculator.

Franz

[emece67]

(12-07-2015 10:56 PM)fhub Wrote:  

(12-07-2015 09:59 PM)emece67 Wrote:  What confused me was the 10/12 limits and using SCI with one limit and ALL with the other.

Well, I've worked quite long on this program and you can be sure that I did it exactly this way for good reason, but don't ask me 4 years later 'why' -
I just don't remember.
And today I'm using the WP34s much less than at that time, so I've already forgotten again lots of the 'special features' of this great calculator.

Franz

Please, don't misunderstand me. Reading your code some things are evident: the big effort needed to code it; and also that there's nothing there by chance, but by deep reasoning and, perhaps, a big amount of trial, test, error & new trials.

In fact, the whole wp34s project looks the same.

Thus my interest in understanding yours (and wp34s in general) code.

Regards.

[Dieter]

(12-07-2015 10:56 PM)fhub Wrote:  And today I'm using the WP34s much less than at that time, so I've already forgotten again lots of the 'special features' of this great calculator.

For instance RSD and RDP. ;-)

The old-style method of rounding that includes changing the display format is not required on the 34s. If you want to round to 12 significant digits, just use RSD 12. And unlike the old method RSD also works for more than 12 digits.

Dieter