ENH: optimize.bisect: improve worst case performance #21535

Hi,
I’ve been working on enhancement to optimize.bisect that can improve its worst case performance. Basically instead of bisecting over the real numbers this method bisects over numbers representable by float64 (you can read more about it here and here). The biggest improvement comes when a user want to search over extreme intervals and with very high precision.

I’ve been chatting under the issue with @j-bowhay about it and I’ve been advised to create and post here some ad hoc benchmarks that would motivate this enhancement. I run optimize.bisect() vs my implementation of the algorithm on the following functions

def f1(x): #[0,1], xtol=5e-324
    return x-1e-20
def f2(x): #[0,1e200], xtol=5e-324
    return x-1e100
e=0.999
M=1e-100
def f3(E): #[0,1], xtol=5e-324
    return E-e*np.sin(E) - M
def f4(x): #[0,1], xtol=5e-324
    sum=0.0
    partial=1.0
    for i in range(1,100):
        partial*=x
        partial/=i
        sum+=partial
return sum-1e-50

and got the results:

My question for you is whether you think that this would be a suitable enrichment for SciPy?
If so, there is a discussion to be had about how to implement the change (for example: should it be available by specifying some parameter in bisect or should it be a different function).

Please let me know what you think :smiley:

Thanks, that’s an interesting approach!

Things I think we’d need to consider:

  1. This is useful in extreme cases, but for a large number of cases the current approach is just fine. So, is the added complexity worth adding and maintaining?
  2. This does not preserve backward compatibility, so we can’t just replace the existing implementation; would probably need to add a flag.
  3. Q: That flag would then need to indicate which floating point dtype will be used in the search?

I see pyroot has two implementations for bisect: pyroot/pyroot/_pyroot_new.py at master · SimpleArt/pyroot · GitHub

bisect_in and bisect_iter — are those the same methods under discussion here?

So just to clarify, my idea was more to follow “work on the double’s bits” route that is guaranteed to end in 64 iterations (more like the example on the codeforces blog I linked above). It’s a bit different than pyroot’s approach with AM and GM. You can see my work in progress implementation here.

Ad 1. So I actually don’t think that the code is very complicated, it mostly would follow the existing bisect implementation, but with a different calculation of the midpoint.

Ad 2. I agree, I don’t want to replace the existing implementation. Right now I’m seeing 2 options: either we add a flag to bisect, or we create an entirely new method that implements this algorithm.

Ad 3. So from what I’ve seen the bisect is right now implemented using C doubles. I think that working purely on doubles is enough for now. If we decide that we like this approach I think that we could discuss supporting other floating point dtypes in the future.

I think it would be useful, and personally I am curious to see the implementation; perhaps a second function would be easiest so there is no confusion? If the function shares a significant amount of internal implementation, worth talking about the flag option more, or about refactoring the internals.

Agreed that double is good as a first pass.

I finished the implementation draft. Take a look when you have a moment :smiley: ENH: optimize.bisect: improve worst case performance by Ambiguouss · Pull Request #26404 · scipy/scipy · GitHub