Root-Seeking Algorithms

General discussion about calculators, SwissMicros or otherwise
Post Reply
jonmoore
Posts: 108
Joined: Mon Apr 13, 2020 4:18 pm

Root-Seeking Algorithms

Post by jonmoore »

Amongst the wealth of root-seeking algorithms that have been written for various HP calculators I've not been able to find one that uses Brent's Method. This is a particular favourite of mine when using Mathematica and I noticed when researching this subject that Paul (of WP43s fame) also lists this as a particular favourite. With that in mind hopefully the WP43s will feature a solver that uses Brent's Method. Maybe it's a method that's hard to write via keystep programming but having the freedom for utilise bespoke C code with the speed benefits of the DM... processor will make this method a more likely possibility.

Ignoring the WP43s, I thought it might be a useful exercise for people to list their favourite solver methodologies on HP calculators (inclusive of the program listings). Maybe some of these solver options will be new to others on the forum, and maybe some will be something that Ángel Martin could include on his Solve & Integrate ROM (HP41cl, DM41x); which contains alternative versions of the classic HP Solve and Integrate algorithms (Secant Method) to those included with SandMath.

There may even be some routines which people like but have found to be too slow for practical calculator use. These will still be useful to know as they may find a new lease of life as C code routines on the WP43s or MCode routines on the 41x (running in Fast/Turbo mode).

A couple of links of interest regarding mathematical methods for numerical analysis in Mathematica (covering more than root finding but still very interesting), and a recent Namir Shammas thread from the Museum which links to lots of interesting solver related white papers and suchlike.

https://reference.wolfram.com/language/ ... rview.html
https://reference.wolfram.com/language/ ... rview.html
https://www.hpmuseum.org/forum/thread-8092-page-2.html

This final link is an excellent solver that Valentín Albillo wrote for the HP-35s. It not only provides results for both real and complex roots, the user only has to provide a single initial guess. In algorithmic terms its efficient, but the sluggish 35s processor doesn't show off the algorithm at it's best. The reason I've included it here as an afterthought is that it uses the 35s's built in Equation Solver as a key aspect of it's algorithm, and on that basis it may be very hard to translate for DM calculator options. Nonetheless, it may prove to be an inspiration to those with the necessary talents. :ugeek:

https://albillo.hpcalc.org/articles/HP% ... 0Roots.pdf
Last edited by jonmoore on Tue May 26, 2020 6:41 pm, edited 1 time in total.
User avatar
pauli
Posts: 251
Joined: Tue May 02, 2017 10:11 am
Location: Australia

Re: Root-Seeking Algorithms

Post by pauli »

The WP 34S uses an updated version of Brent's method. In addition to the inverse quadratic, bisection and secant steps that Brent's use, it will also undertake steps of Ridder's method.

Ridder's method is good but needs the root to be bracketed and isn't quite as general Brent's method.

On the 34S, the solver is implemented as a keystroke program. The solving part was straightforward. The messy bit was behaving like the solver on the older HP calculators: handling errors, single root guesses, apparently constant functions.


Pauli
jonmoore
Posts: 108
Joined: Mon Apr 13, 2020 4:18 pm

Re: Root-Seeking Algorithms

Post by jonmoore »

Thanks Paul, that's exactly the news I was hoping to hear.

Strangely, I've never explored the solver on the 34s as I mainly use it for statistical stuff with DBLON enabled (for calculations where the increased precision is essential). I'll be sure to explore it now I know the methodology it uses. However, making use of the same solver written in C on the 43s is a far more enticing prospect!
User avatar
Walter
Posts: 3070
Joined: Tue May 02, 2017 11:13 am
Location: On a mission close to DRS, Germany

Re: Root-Seeking Algorithms

Post by Walter »

@jonmoore: Since Valentin Albillo is no active member of this forum - and isn't planning to become one for the time being - he asked me elsewhere to post the following response on his behalf:
Hi, jonmoore,

I've just seen your message "Root-seeking algorithms" posted last Tue May 26, 2020 11:42 am, where you mention my HP35s solver featured in my article "Boldly Going ... Going Back to the Roots", and though I thank you very much for your interest and your kind words re my program, I must indicate that you're making a wrong statement when you say, I quote,

"[...] it uses the 35s's built in Equation Solver as a key aspect of it's [sic] algorithm"

which is utterly untrue. My program does not use the built-in Equation Solver at all, as it's plain from both the program listing as well as the whole documentation in the PDF article. Matter of fact, I wonder why did you reach that conclusion.

Also, when you add "on that basis it may be very hard to translate for DM calculator options", this conclusion is also throroughly misguided as "that basis" is untrue to begin with.

I'd appreciate it if you would either edit out or retract the wrong parts from your message.

Thanks in advance.
V.
WP43 SN00000, 34S, and 31S for obvious reasons; HP-35, 45, ..., 35S, 15CE, DM16L S/N# 00093, DM42β SN:00041
whuyse
Posts: 197
Joined: Thu Dec 21, 2017 1:23 pm

Re: Root-Seeking Algorithms

Post by whuyse »

jonmoore wrote:
Tue May 26, 2020 11:42 am
This final link is an excellent solver that Valentín Albillo wrote for the HP-35s. It not only provides results for both real and complex roots, the user only has to provide a single initial guess. In algorithmic terms its efficient, but the sluggish 35s processor doesn't show off the algorithm at it's best. The reason I've included it here as an afterthought is that it uses the 35s's built in Equation Solver as a key aspect of it's algorithm, and on that basis it may be very hard to translate for DM calculator options. Nonetheless, it may prove to be an inspiration to those with the necessary talents. :ugeek:

https://albillo.hpcalc.org/articles/HP% ... 0Roots.pdf
Not hard at all, I wrote that a couple of years ago, see here
Be sure to use the version at the end, without local variables (save REGS).
Cheers, Werner
41CV†,42S,48GX,49G,DM42,DM41X,17BII,15CE, DM15L
Post Reply