I am looking for an algorithm to do the following.
Given:
- An interval $[a,b]$.
- A black box function $n(x)$ which returns the number of roots (zeros) of a function that lie to the left of $x$. That is, for some function $f(y)$, $n(x)$ returns a count of all $y$ such that $f(y)=0$ and $y
.
Find: Approximations to all of the roots of the function in $[a,b]$ using few invocations of $n(x)$.
It would be nice if there was a tunable parameter to trade off accuracy of approximations and the number of invocations. Also, it is sufficient to indicate a cluster of nearby roots without resolving all of them.
Quick edit: I know about algorithms like bisection, which work for single roots. I'm wondering if wanting all the roots at once might save on function invocations.