Root-Seeking Algorithms

General discussion about calculators, Swiss Micros or otherwise
Post Reply
jonmoore
Posts: 106
Joined: Mon Apr 13, 2020 2:18 pm

Root-Seeking Algorithms

Post by jonmoore » Tue May 26, 2020 9:42 am

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 4:41 pm, edited 1 time in total.

User avatar
pauli
Posts: 102
Joined: Tue May 02, 2017 8:11 am
Location: Australia

Re: Root-Seeking Algorithms

Post by pauli » Tue May 26, 2020 10:32 am

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: 106
Joined: Mon Apr 13, 2020 2:18 pm

Re: Root-Seeking Algorithms

Post by jonmoore » Tue May 26, 2020 11:57 am

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!

Post Reply