Bracket and Solve Root

template <class F, class T, class Tol>
std::pair<T, T>
   bracket_and_solve_root(
      F f,
      const T& guess,
      const T& factor,
      bool rising,
      Tol tol,
      boost::uintmax_t& max_iter);

template <class F, class T, class Tol, class Policy>
std::pair<T, T>
   bracket_and_solve_root(
      F f,
      const T& guess,
      const T& factor,
      bool rising,
      Tol tol,
      boost::uintmax_t& max_iter,
      const Policy&);

bracket_and_solve_root is a convenience function that calls TOMS 748 algorithm internally to find the root of f(x). It is generally much easier to use this function rather than TOMS 748 algorithm, since it does the hard work of bracketing the root for you. It's bracketing routines are quite robust and will usually be more foolproof than home-grown routines, unless the function can be analysed to yield tight brackets.

Note that this routine can only be used when:

f(x) is monotonic in the half of the real axis containing guess.
The value of the inital guess must have the same sign as the root: the function will never cross the origin when searching for the root.
The location of the root should be known at least approximately, if the location of the root differs by many orders of magnitude from guess then many iterations will be needed to bracket the root in spite of the special heuristics used to guard against this very situation. A typical example would be setting the initial guess to 0.1, when the root is at 1e-300.

The bracket_and_solve_root parameters are:

f: A unary functor that is the function whose root is to be solved. f(x) must be uniformly increasing or decreasing on x.
guess: An initial approximation to the root.
factor: A scaling factor that is used to bracket the root: the value guess is multiplied (or divided as appropriate) by factor until two values are found that bracket the root. A value such as 2 is a typical choice for factor. In addition factor will be multiplied by 2 every 32 iterations: this is to guard against a really very bad initial guess, typically these occur when it's known the result is very large or small, but not the exact order of magnitude.
rising: Set to true if f(x) is rising on x and false if f(x) is falling on x. This value is used along with the result of f(guess) to determine if guess is above or below the root.
tol: A binary functor that determines the termination condition for the search for the root. tol is passed the current brackets at each step, when it returns true then the current brackets are returned as the pair result. See also predefined termination functors.
max_iter: The maximum number of function invocations to perform in the search for the root. On exit is set to the actual number of invocations performed.

The final Policy argument is optional and can be used to control the behaviour of the function: how it handles errors, what level of precision to use etc. Refer to the policy documentation for more details.

Returns: a pair of values r that bracket the root so that:

f(r.first) * f(r.second) <= 0

and either

tol(r.first, r.second) == true

max_iter >= m

where m is the initial value of max_iter passed to the function.

In other words, it's up to the caller to verify whether termination occurred as a result of exceeding max_iter function invocations (easily done by checking the value of max_iter when the function returns), rather than because the termination condition tol was satisfied.