1
$\begingroup$

A boolean-valued function 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 (a closed-form equation producing these binary-valued outputs is unknown, since it is the result of a time-domain simulation of complicated system of non-linear PDEs meeting certain exit conditions etc.). Furthermore, $\frac{\partial{f}}{\partial{n}}$ is also obviously 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 naive 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 enter image description here

$\endgroup$
  • $\begingroup$ Are $n_{min}$ and $n_{max}$ known? ​ ​ $\endgroup$ – user12859 May 17 '17 at 1:16
  • $\begingroup$ Yes. Maybe the sentence is buried deep in the question that it's not clearly visible. $\endgroup$ – Krishna May 17 '17 at 1:17
  • 4
    $\begingroup$ en.wikipedia.org/wiki/Binary_search_algorithm#Algorithm ​ ​ $\endgroup$ – user12859 May 17 '17 at 1:18
  • 1
    $\begingroup$ Monte Carlo approach could be useful in practice. I want to add, that if functions doesn't have any property which we can exploit then there is no free lunch, i.e. checking one by one is the best you can do. If you function is monitonically non-decreasing(if I see it correctly from your question), then golden search is the way to go. It should outperform binary search. $\endgroup$ – Eugene May 17 '17 at 1:42
  • 1
    $\begingroup$ Binary search is the best you can do if you don't know anything about $n^*$. It has the best worst-case guarantee. There may be a better algorithm in practice (probably start with a heuristic and finish with binary search) if you have information about $n^*$. But whether such heuristics are worth exploring depends entirely on what you know about $n^*$. You may want to ask a follow-up question about that, where you give the details of what $f$ is. $\endgroup$ – Gilles 'SO- stop being evil' May 17 '17 at 11:59
2
$\begingroup$

Use binary search.

You know that the correct value is somewhere in the range $[n_\min,n_\max]$, so pick $t = \lfloor (n_\min+n_\max)/2 \rfloor$ (the point halfway in the middle), and evaluate $f(t)$. This will either tell you that $n^*$ is in $[n_\min,t]$ or that $n^*$ is in $[t+1,n_\max]$. Now you can repeat on the smaller interval. Each time, the width of the interval decreases by a factor of two, so after $\lg (n_\max-n_\min)$ iterations, you will find the correct value of $n^*$. This is much faster than trying all $n_\max-n_\min$ possible values of $n^*$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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