Simply Beautiful Art

@MartinSleziak Seems good yeah

@XanderHenderson Thanks again =/

@XanderHenderson I think they learned nothing from last time =/

@user21820 Yeah

Yeah

Honestly also not sure about how to fit your method into other brackets, like say $(5, 10^{100})$.

@user21820 I mean it depends on the provided bracket's size.

As a fun aside, $(\exp(x+20)-2) (1+10^{-10} + \sin(\ln(1+x^2)))$ with an initial bracket of $(-a,0)$ is quite a nasty test case for many bracketing method implementations. It tricks stuff like Brent's method into trying interpolation search repeatedly.

@user21820 I meant you still have to check the endpoints. You may not find any sign changes during your steps, and there's no other way to determine which side (towards $0$ or $\pm\infty$) should the root lie in. Besides, verification of a valid bracket is necessary for many methods (particularly those involving interpolation needing the actual values).

Well I mean I can try implementing yours anyways and see how that'll fit in with everything else.

@user21820 The intended usage is that one may use $(-\infty,\infty)$ and similar as initial brackets, which gets "rounded down". Usually these points aren't computed but rather provided, either as asymptotic real value or $\pm\infty$. There isn't a clear guarantee that I see with your approach that any bracket will be found though, without such an assumption beforehand.

Still think mine tends to be faster though. And a bit more natural in the sense of bracketing.

Hmm well it is only 10 iterations for double precision.

@user21820 I think this also has issues with solutions very close to $0$.

Say for example our bracket is $(2,2^{1024})$ so that $LM(\dots)=2^32$. If this is insufficient, the next iteration or 2 should already give a sufficient bracket.

Well it pulls in values from the opposite side of the bracket a lot faster, usually in only 2 to 5 iterations I'd say. Even if the interval is still large, interpolation search might still be applicable.

Some methods, like Chandrupatla's method, will be able to decide when interpolation search seems feasible on their own, but they tend to require both sides of the bracket to be somewhat reasonable.

Worth noting that aside from quickly converging, bracketing both sides of the root is fairly important, which is the main reason I'm not so hot on the idea of searching outwards from the smaller side.

Idk how I feel about the doubly-exponential search, it still feels a little wonky to me.

@user21820 That's just GM lol

Yeah, but I haven't really much better ideas.

As far as the bisection goes, it also involves swapping over to $AM$ once $x\in[y/4,4y]$, and it also involves minimum tolerance steps so that you don't just get stuck at something like $x=1$ on every step but instead move over to something like $1\pm10^{-13}$ or something.

$LM(x,y)=\operatorname{sign}(x) \exp(GM(\ln|x|,\ln|y|))$ if $\operatorname{sign}(x) =\operatorname{sign}(y)$.

$LM(x,y)=0$ if $\operatorname{sign}(x) \ne\operatorname{sign}(y)$.

$GM(x,y)=\operatorname{sign}(x) \sqrt{xy}$ if $\operatorname{sign}(x) =\operatorname{sign}(y)$.

$GM(x,y)=0$ if $\operatorname{sign}(x) \ne\operatorname{sign}(y)$.

The full formulation that I used was:

@user21820 I mean whether or not it really is expensive in comparison depends on how expensive your function evaluations are in comparison. I also think that in a lot of problems, it tends to be more expensive to evaluate large inputs than smaller inputs, or it can be troublesome to deal with due to overflow.

@user21820 Yeah that's right, but practically speaking most problems do not have large exponents. Even if such a problem did involve large exponents, the suggested mean is still fast converging, especially considering that the double does not have very many exponents to search through.

[cont.] in only say 4 or 5 iterations to the right order of magnitude, which is very satisfactory.

In the context of double precision, my "log mean" tends to converge on an interval of roughly $(2,2^{1024})$

So such methods are not as good as far as I've seen.

I think I've also tried exponential searching in the past but in terms of the rate at which it converges to the right order of magnitude, it's only guaranteed to be about as the arithmetic mean, except it starts from the smaller side.

$LM(x,y)=10^{100}$

$GM(x,y)= 10^{505}$

$AM(x,y)\approx 5\times10^{999}$

For example, with $x=10^{10}$ and $y=10^{1000}$, we have:

The formula for $x,y>1$ is $\exp(\sqrt{ \ln(x)\ln(y)})$.

And so I came up with the idea of "log-log-scaling" things to accelerate convergence to smaller values while retaining both asymptotically optimal convergence (arithmetic mean) and fast convergence to the right order of magnitude (geometric mean).

The big downside to it in a practical setting, most solutions tend to have an order of magnitude around zero. It's not every day that reaching $|x|\approx10^{\pm100}$ isn't just asymptotic behavior.

Previously I mentioned the idea of using the geometric mean in a numbering system similar to scientific notation which scales exponentially.

Also came up with a cool bisection variant.

@user21820 lmao that is an oof

The only downside is that my code now has a bunch of try..except blocks haha

And then use bisection if all else fails.

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.

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

Estimate at least twice with interpolation search methods.

Currently my procedure is as follows:

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