next up previous contents index CD CD Algorithms
Next: Exercises Up: Divide and Conquer Previous: Binary Search

Square and Other Roots

The square root of n is the number r such that tex2html_wrap_inline24874 . Square root computations are performed inside every pocket calculator, but it is instructive to develop an efficient algorithm to compute square roots.  

First, observe that the square root of tex2html_wrap_inline24876 must be at least 1 and at most n. Let l=1 and r=n. Consider the midpoint of this interval, m=(l+r)/2. How does tex2html_wrap_inline24884 compare to n? If tex2html_wrap_inline24886 , then the square root must be greater than m, so the algorithm repeats with l=m. If tex2html_wrap_inline24890 , then the square root must be less than m, so the algorithm repeats with r=m. Either way, we have halved the interval with only one comparison. Therefore, after only tex2html_wrap_inline24894 rounds we will have identified the square root to within tex2html_wrap_inline24896 .

This bisection method, as it is called in numerical analysis, can also be applied to the more general problem of finding the roots of an equation. We say that x is a root of the function f if f(x)=0. Suppose that we start with values l and r such that f(l) > 0 and f(r) < 0. If f is a continuous function, there must be a root between l and r. Depending upon the sign of f(m), where m=(l+r)/2, we can cut this window containing the root in half with each test and stop when our estimate becomes sufficiently accurate.  

Root-finding algorithms that converge faster than binary search are known for both of these problems. Instead of always testing the midpoint of the interval, these algorithms interpolate to find a test point closer to the actual root. Still, binary search is simple, robust, and works as well as possible without additional information on the nature of the function to be computed.

Mon Jun 2 23:33:50 EDT 1997