1
$\begingroup$

A Boolean function $f(n)$ is defined in the set of positive integers, $\mathcal Z$.

$$f(n) = \begin{cases} 0, &n_{min}\le n < n\ast\\1, &n\ast\le n\le n_{max} \end{cases} ; n \in \mathcal Z $$

$f(n)$ is computationally expensive and it's analytical form that produces the binary-valued output is unknown (the Boolean outputs are the result of time-domain simulation of complicated strongly non-linear PDEs meeting certain exit conditions etc.). Obviously, analytical form of $\frac{\partial{f}}{\partial{n}}$ is also not available.

The goal is to compute $n\ast$, i.e. the first occurrence of the integer-valued function input, $n$ that produces a Boolean $1$. Needless to say, this can be trivially achieved in computer code by using a simple $for$ loop and rejecting the values of $n$ one by one, until we hit $n\ast$. The lower and upper bounds, $n_{min}$ and $n_{max}$ are known apriori.

However, given the expensive nature of computing $f(n)$, I am looking for an efficient algorithm beyond this naïve implementation, especially one that requires small number of function evaluations. A pseudo-code implementation of your proposed solution would be much welcome too.

A conceptual schematic/visualisation of the problem is also shown here, purely to aid the understanding of the task at hand. simplified illustration

$\endgroup$
  • 1
    $\begingroup$ Why not just a binary search? Are you looking for something faster? $\endgroup$ – John Lou May 17 '17 at 0:34
  • $\begingroup$ I am looking for something faster than worst logarithmic convergence. Also, since I am a newbie in such implementations, I am a bit confused that the presence of such duplicate elements (strong duplicity, just a vector of 0s and 1s, right) might throw the algorithm off-track, for example the comment here by the author of a MATLAB implementation says "There is no way to predict how the function will behave if there are multiple numbers with same value". Furthermore, I don't have a sorted array/list of values to start off. The function evaluations are a big pain. So, such concerns. $\endgroup$ – Dr Krishnakumar Gopalakrishnan May 17 '17 at 0:40
  • $\begingroup$ I'm pretty sure that there is not really anyway to be faster than binary search, especially given these conditions. You might want to look at hash tables, but I don't think that applies in your situation. $\endgroup$ – John Lou May 17 '17 at 0:55
  • $\begingroup$ I'm voting to close this question as is has been subsequently asked on Computer Science: Search algorithm to find integer input that produces the first 'True' (bool: 1) occurence of a computationally expensive boolean function. $\endgroup$ – user642796 May 17 '17 at 9:11
1
$\begingroup$

I doubt that you can do better than the logarithmic time of binary search. But if the cost of your expensive calculation depends on $n$ in some easily computable way you might be able to speed things up by doing a binary search that splits the remaining interval nearer the low than the high end, trading shorter computation time for perhaps more iterations - still worst case logarithmic, but perhaps with better constants or better average behavior.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ ok. Good point. The computation time per function evaluation is roughly a linear function of $n$ plus a constant bias for $n_{min}$. I suppose, it's really hard to split the interval purely based on such hand-way numbers as the leading coefficient, $c$ for the $\mathcal {O} (c \log n)$ computation cannot be accurately computed anyway. $\endgroup$ – Dr Krishnakumar Gopalakrishnan May 17 '17 at 1:07
1
$\begingroup$

Here's some pseudocode that I would suggest. Not sure if that helps or not, though.

Method int binarySearch(min, max)

int x = (min + max)/2;

if (max - 1 = min)

$\quad$ return max

if f(x) = 1

$\quad$ binarySearch(min, x)

else

$\quad$ binarySearch(x, max)

| cite | improve this answer | |
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.