@SimplyBeautifulArt Can't you just take n-th root where n is odd and larger than the order of the desired root?

Then any algorithm that works with simple roots will work!

@user21820 lol no, e.g. $\operatorname{signedexp}_{1/2}(x) = \operatorname{sign}(x)\sqrt{|x|}$ is not a simple root.

Or even something like the cube root is not so nice.

@SimplyBeautifulArt Couldn't you use \exp??

What does signedexp mean?

Oh you're defining it?

I'm defining it to be $\operatorname{signedexp}_a(x) = \operatorname{sign}(x)|x|^a$ for the sake of bracketing.

Well the point is that cube-root of that would have only a simple root, so any fast-converging algorithm would work.

Oh whoops!

I see what you mean. It's infinite gradient.

I have no idea what I was thinking when I said "take n-th root ...". Ignore me...

Yeah, plus even if I can rapidly pull in one estimate of the root, the hard part is getting both ends near it.

@user21820 Originally I thought of the same idea. I think if one were able to estimate the order of the root, a corrective factor is possible. For example, there's $x_{n+1}=x_n-df(x_n)/f'(x_n)$ for the extended Newton's method, where $d$ is the order of the root. It also works for things like $\sqrt[3]{x}$.

@SimplyBeautifulArt But you don't like derivatives, correct?

There's also applying the secant method to $f(x)/f'(x)$ once you're very close to the root, since that turns it into a simple root, but the problem is that I'm trying to avoid $f'(x)$.

Yeah

@SimplyBeautifulArt What method do you have that is faster than binary/interpolation search that does not use derivatives?

@user21820 I don't haha

@user21820 I also tried estimating $f'(x)$ with secant lines from the iterations, but that didn't work very well considering the nature of $f'(x)$ near these types roots.

Lol then why not just go with n-th root? It actually works then because you don't need finite derivative at that point for the interpolation method to work.

@user21820 I don't know how one would estimate the order of the root, and over-estimating it is not good either

Double and dovetail? =D

Pardon? o.o

If you don't know the true order, you can dovetail multiple solvers where the k-th solver is using (2^k−1)-th root where k∈ℕ+. Dovetailing means that you ensure that the solvers run in parallel and that if it runs forever then eventually a solver will start for every k∈ℕ+.

The roughly doubling means that you don't waste too much resources trying every order.

hahaha

I would wager that'd it be better to after every iteration, given $x_m,x_p$ and $x_s$ between $x_m$ and $x_p$, find the order $d$ of the root which makes the 3 points collinear, would be a better method.

Interesting idea.

But I think it's very prone to failure.

In the sense that if you just happen to test a part of a function that tricks that order-estimate...

It reminds me of Ridder's method actually lol, which is in fact prone to... not be as good as one might claim it to be.

Whereas my idea, although rather wasteful, will never fail badly in the sense that it will exhaustively crank all the solvers so the right one will be found quite quickly unless the root has super-exponential order!

@user21820 The way my code works is it has some "safelocks" where it'll push a bisection iteration if it fails to progress sufficiently fast too many times in a row.

Ah yea but you want it to also converge on the optimal convergence right? =)

yeah yeah

Does the idea make sense? I've actually used such a doubling technique before to obtain an optimal algorithm from an algorithm that needs to know some parameter, but I can't compute the parameter efficiently!

I've certainly tried it on some things before. Not really sure if I want to be using it here haha

Haha..

@SimplyBeautifulArt There are various complex methods you can try to optimize such a dovetailing method. For example, call an n-step to be an interpolation step using the n-th root. Then you can start with the 1-step and keep track of the performance of every n-step and according to the past performance over the steps taken so far you can choose which n-step to use next.

The idea is that in ordinary cases it will take mostly 1-steps and some 3-steps (which it finds are less efficient). And in the 'bad' cases it will take higher n-steps more often if the 1-steps perform badly.

@SimplyBeautifulArt To an extent this definitely worked.

Now the problem is juggling the fact that it harms the convergence when the root is actually simple lol

Although it approaches an order estimate of 1, you lose some of the speed with it.

Currently my procedure is as follows:

Estimate at least twice with interpolation search methods.

If it converges too slow, on the 3rd attempt, try modifying it with the order, which is estimated every iteration.

If it still converges too slow, on the 4th attempt, try an "over-stepping" method (e.g. double the distance moved) in case just one side of the bracket is rapidly converging.

And then use bisection if all else fails.