# Algorithm to approximate roots using blackbox root counting function

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<x$.

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.

-
Just use bisection: divide and conquer. – user16697 Dec 29 '11 at 10:57
Just to clarify: $f$ is a continuous function with a finite number of roots in $[a,b]$, right? As to QED's comment, I think he meant bisection on $n(x)$ (not on $f(x)$), which involves finding $y \neq x$ with $n(y) \neq n(x)$. – Pedro M. Dec 29 '11 at 11:11

## 1 Answer

An obvious algorithm is to look at $n(a)$ and $n(b)$. If the difference is positive then go ahead as the interval is "in play".

Look at $n\left(\frac{a+b}{2}\right)$. If this is equal to either $n(a)$ and $n(b)$ then half the interval is no longer in play; otherwise both halves are in play.

Continue subdividing the subintervals which are in play until your appoximations are close enough.

-