Binary search to find nth root of a number

Question

I tried implementing a function using binary search to solve the following :

Implement a function root that calculates the n’th root of a number. The function takes a non negative number x and a positive integer n, and returns the positive n’th root of x within an error of 0.001 (i.e. suppose the real root is y, then the error is: |y-root(x,n)| and must satisfy |y-root(x,n)| < 0.001). The key is to find the root without using the STL function.

My code:

double binarysearch(double left,double right, double x, int n){
 while(left<right){
  double mid = left + (right-left)/2;
  double answer = pow(mid,n);
   if(fabs(answer - x ) <= DELTA)
    return mid;
  else if(answer > x )
      right = mid - DELTA;
  else 
     left = mid + DELTA;
 }
  return -1;
}

This reaches a condition where left>right and it returns -1.

Is there a way to implement this using binary search?

Try debugging, e.g. by printing the values of your variables at each step. — jkff, Feb 27 '18 at 01:25
Note that binary search is the wrong term. You're not searching for a specific value in a list. You should be searching for _any_ y within DELTA of x^(-n)., i.e. numbers near a root y of y^n - x = 0, fabs(y - x^(-n)) < DELTA. The algorithm to do this is called _bisection_. If you use this as a search term, you'll get lots of hits and many examples of correct implementations. @MattTimmermans answer gets the same answer for this specific problem, but the bisection algorithm will work for finding roots x of a very large class of functions f(x)=0. — Gene, Feb 27 '18 at 05:24
try/port this [How to get a square root for 32 bit input in one clock cycle only?](https://stackoverflow.com/a/34657972/2521214) it uses binary search with highly optimized approach (no multiplication needed) there are a lot of other similar methods like [How approximation search works](https://stackoverflow.com/a/36163847/2521214) the other answer there describes bisection which this code use ... And then there are also approximation methods too. also see [Power by squaring for negative exponents](https://stackoverflow.com/a/30962495/2521214) for the full bin search vs squaring stuff — Spektre, Feb 27 '18 at 08:59

Matt Timmermans · Accepted Answer · 2018-02-27T03:46:46.693

Your function breaks because the difference between (mid-DELTA)^n and mid^n is usually more than DELTA.

Binary search with doubles can be tricky, and there are various ways to do it depending on what result you really want. In this case, you are asked to give an answer within 0.001 of the actual root. It is not required that your answer^n is within 0.001 of x.

That suggests an implementation like this:

double binarysearch(double x, int n)
{
    double lo = 0.0;
    double hi = x;
    while(hi-lo >= 0.0019)
    {
        double test = lo+(hi-lo)*0.5;
        if (test == low || test == hi)
        {
           //I couldn't bear to leave this out.  Sometimes there are no
           //double values between lo and hi.  This will be pretty much
           //as close as we can get.  Break here to avoid an infinite loop
           break;
        }
        if (pow(test,n) < x)
        {
            lo = test;
        }
        else
        {
            hi = test;
        }
    }
    //cut the final range in half.  It's less than
    //0.0019 in size, so every number in the range, which includes
    //the root, is less than 0.001 away from this
    return lo+(hi-lo)*0.5;
}

Notice that there is no possibility to return "not found"

Binary search to find nth root of a number

1 Answers1