Binary search in "infinite" sequence. Where to begin?

Question

I have an interesting problem. I came across a function that takes a long time to calculate a value based on some index. Name it takes_a_long_time(index) . The values ​​returned by this function are guaranteed to have a global minimum, but there is no guarantee that the index associated with it will be close to zero.

Since takes_a_long_time accepts arbitrarily large positive numbers as its index, there are unique restrictions on how to start a binary search. I need a way to create a finite search interval for an exact minimum. My first thought was to check for ever larger intervals, starting from zero. Sort of:

 def find_interval_with_minimum(): start = 0 end = 1 interval_size = 1 minimum_in_interval = check_minimum_in(start, end) while not minimum_in_interval: interval_size = interval_size * 2 start = end end = start + interval_size minimum_in_interval = check_minimum_in(start, end) return start, end 

It would seem that this works fine, but there is additional information that really drops things. takes_a_long_time takes exponentially more time to calculate the value, as the indices are approaching zero. Since check_minimum_in will require several calls to takes_a_long_time , I would like it to not start from scratch.

So my question is that the minimum can be anywhere at [0, + infinity), is there a reasonable way to run this “back”? Or is there a good heuristic to avoid checking low indexes if this is not necessary?

I would like a language agnostic solution. However, I am writing this in Python, so if there is a specific approach to python, I would accept this as well.

Answer 1

From the comments on the question, the curve behaves well, and you can use something like triple search . The only problem is how to deal with uncomfortable behavior when your approach is zero. Therefore, don't start from scratch: define a new function g from your function f with g(x) = f(1/x) . Find this beginning with x=0 and a small value, doubling or otherwise increasing the size of the interval until it contains a minimum.

To do this, you need to know the limit of f , as its argument approaches infinity, or the equivalent limit of g , since its argument is zero. If it cannot be estimated explicitly, I will try a numerical approximation.

See comment comments for some points to keep in mind on how to increase interval size, especially Steve Jessop.

Answer 2

It seems like you need to do to select a large quantity large enough so that takes_a_long_time not too long acceptable. Start two streams: one that starts to look towards positive infinity for the range containing the minimum, and the other that starts to look down to zero for the range containing the minimum. Due to the exponential increase in time, 0 can also be infinite with respect to the search. Which thread will find the result, cancel the other.

But then, if you do not want to use several processor cores, do not start two threads (and if you do, do not start exactly two threads, start one on the core or so). Just alternate the work on the side or in another.

Given this basic strategy, now you need to adjust the speed at which you are approaching. The faster you approach it, the fewer steps to find a minimum if it is really on that side, but the larger the range that remains binary because on average you "exceed" further to zero. If the performance curve is mutually exponential, then apparently you want to overshoot as little as possible, so get very close to 0. Perhaps even your task is computationally impossible, “exponential” often means “impossible”.

Obviously, I can’t say anything about what should be the initial “big number”. One hundred tolerant? Is it a million? Graham number? If you don’t even know what might have acceptable performance, you can find out by working in parallel (again, through threads or through matching) a set of takes_a_long_time calculations for different indices until one of them completes. Again, there is no guarantee that this is possible from a computational point of view - if every index that fits into your computer’s memory takes at least a billion years, you are stuck in practice, although theoretically you have a theoretical solution.