An infinite precision bracketing algorithm with guaranteed convergence

The computational cost of a bracketing algorithm in the bit model of computation is analyzed, when working with a finite arithmetic of unbounded accuracy. The complexity measure used here is the number of bit operations, seen as a function of the required absolute error of the result. In this model the convergence of the classical bisection method (as well as that of any bracketing method which requires the function sign) is not ensured when no information on the behaviour of the function is available. A modified bisection algorithm with guaranteed convergence is proposed and an upper bound to its computational cost is given.