Quickly finding the first point at which a function equals 0 using scipy.optimize

Question

Basically, given a function that produces outputs like this for different parameters:

I want to quickly find the first x at which the function equals 0. So with parameters that produce the blue curve over x, I want to find x=134. For the green curve, I want to find x=56, etc.

I think the function will always be monotonically decreasing until it hits zero, but I'm not totally sure.

The function is not necessarily monotonically decreasing.

I am sure that it will only hit 0 once, and then remain zero.

Currently I'm brute-forcing it by iterating through x values until I hit zero, but I want something that will be better at making educated guesses (based on slope?) and iterating.

Ideally I want to use something already-baked (since 90% of programmers can't even write a binary search correctly), like something from scipy.optimize, but it seems like those all want to find either a global minimum or a zero-crossing.

(This function is sort of a distance_to_the_wall of the RGB cube for a given chroma in Lch color space (so basically building a "sanely clip to RGB" function), but since the mapping between IRGB and LCh can vary by library and with parameters like illuminant etc. I think it's best to just try a few values until the right one is found rather than trying to reverse-calculate the value directly?)

Answer 1

Here is some code to flesh out @ExP's bisection/binary search answer:

def find_first_zero(func, min, max, tol=1e-3):
    min, max = float(min), float(max)
    assert (max + tol) > max
    while (max - min) > tol:
        mid = (min + max) / 2
        if func(mid) == 0:
            max = mid
        else:
            min = mid
    return max

Answer 2

Try bisection: Check if it's 0 in the middle of your interval; if it is, continue on the left, otherwise, on the right. Do the same thing with the reduced interval recursively until you're close enough. This method is of complexity O(log n) compared to yours, which is O(n).

Answer 3

If not for the fact that the right hand of the curve is 0 everywhere, Newton's method ( https://en.wikipedia.org/wiki/Newton's_method ) would work great. But I think a variant will still work fine:

1) Pick a point.

2) If we are on a slope, take the gradient of the slope locally and trace a line from there to the x intercept and take this as your new point (go to 1) ).

3) If we are on the flat plain (x = 0, derivative = 0), then if a bit to the left is a slope (would have to tune this to figure out how much left to check), then do a local search (probably binary search with tolerance) to find the point at which the function first equals zero. If not, then take the point that is the middle between this point and the last point on a slope we tried (go to 1 with this new point).

To estimate the derivative (to determine if you are on a slope or not), you can sample a point to the left and to the right, just far enough away that you're confident you'll get a smooth approximation of the derivative.