Heads up for a hot new root seeking algorithm!!

[emece67]

(01-24-2017 07:05 PM)Mike (Stgt) Wrote:  After some tests I am able to answer my question on my own. The classical Newton wins the race for square and forth root, the later even when computing it by Sqrt(Sqrt(x)).

In my case, to compute 4th roots to 10000 digits the Newton-Raphson method needed around 15 iterations (30 function evaluations) whereas the Ostrowsky-Traub uses 8 iterations (24 function evaluations). The OT method requires also less time (75.6 ms vs 81.4 ms). I'm working in Python with the mpmath package.

I've also checked the Halley method (10 iterations, 30 function evaluations, 78.7 ms, still faster than NR) and the Potra-Ptak method (the 3rd order one, 11 iterations, 33 functions evaluations, 101.6 ms, the slower one, curious, as this method seems quite simple).

I've not found such dramatic speed-ups between methods as you have found, the difference between my fastest (OT) and slowest (PP) is just 1.35x. No "sliding accuracy" in my case.

Regards.