BlogsDope image BlogsDope

Find the cube root of a number

Given a number N, find its cube root upto a precision P where N>=1.

Example: INPUT: N=3, P=2
OUTPUT: CubeRoot of 3 is 1.44

INPUT: N=125, P=2
OUTPUT: CubeRoot of 125 is 5.0

Brute Force Approach


The brute force approach is to iterate over the natural numbers from 1 to N and check if their cubes are equal to N. This approach will suffice if N is a perfect cube. But if N is not a perfect cube, the brute force approach is carried out in two steps,

1. While iterating from 1 to N, find the closest integer such that  (closest+1)*(closest+1)*(closest+1) is greater than N,

Int close = 1;

for (int i = 1; i <= N; i++)
{ // break if i*i*i is greater than N
    If(i * i * i > N)
    {
        close = i - 1;
        break;
    }
}
.
// Check if N is a perfect cube. If it is, then return close.
if (close * close * close == N) return close;

2. Now iterate for the fraction part upto the given precision P as shown below.

double increment = 0.1

for (int i = 0; i < P; i++)

{ // increment close until “close” is greater than N.
    while (close * close * close <= N)
    {
        close += increment;
    }

    // when close*close*close is greater than N, remove the latest increment.
    close -= increment;

    // Go for further precision
    increment /= 10;
}

return close;

The time complexity of the above approach is the sum of the complexity of the integral part and the fractional part i.e  $O(N) + ≍O(10P)$.

Using Binary Search


We can use binary search between 1 to N to solve the above problem,

Follow below Steps/Algorithm:

1. Initialize low = 1 and high = N.

2. Convert P to the order of its precision value in decimal format. For eg. if P=2, the order is 0.01. Assign its value to a variable prec.

3. While low is less than or equal to high, repeat steps 4 to 7.

4. Find the middle number between low and high i.e. mid and assign it to a variable cuberoot.

5. Check if mid*mid*mid is close enough to N such that their absolute difference error is less than prec.

6. If step 5 condition is true, exit the loop and go to step 8.

7. Check, if mid*mid*mid exceeds N. If it does, then reduce high to mid. Or, if mid*mid*mid is less than N, then increase low to mid.

8. Convert cuberoot such that it has the exact precision after the decimal point. (In many cases, the cuberoot will result into more accurate value than desired. Therefore, this step is necessary.)

9. Return cuberoot.

  • C++
  • Python
  • Java
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

double cubeRoot(double N, int P)
{
    double low = 1;
    double high = N;
    double prec = pow(10, -P);
    double cuberoot = 1;

    while (low <= high)
    {
        double mid = (low + high) / 2;
        cuberoot = mid;

        // if the difference between cube of current mid and N is less than precision, then break.
        if (fabs(mid * mid * mid - N) <= prec)
            break;

        // decrementing high if answer lies between current low and mid
        else if (mid * mid * mid > N)
            high = mid;

        // incrementing low if answer lies between mid and current high.
        else
            low = mid;
    }
    return round(cuberoot * pow(10, P)) / pow(10, P);
}
# cubeRoot Method
def cubeRoot(N, P):
    low = 1
    high = N
    prec = 10 ** (-P)

    while low <= high:
        mid = (low + high) / 2
        cuberoot = mid

        # if the difference between cube of current mid and N is less than precision, then break.
        if abs(mid * mid * mid - N) <= prec:
            break

        # decrementing high if answer lies between current low and mid
        elif mid * mid * mid > N:
            high = mid

        # incrementing low if answer lies between mid and current high.
        else:
            low = mid
    return round(cuberoot, P)
double cubeRoot(double N, int P) {
  double low = 1;
  double high = N;
  double prec = Math.pow(10, -P);
  double cuberoot = 1;
  while (low <= high) {
    double mid = (low + high) / 2;
    cuberoot = mid;

    // if the difference between cube of current mid and N is less than precision
    // value, then break.
    if (Math.abs(mid * mid * mid - N) <= prec)
      break;

    // decrementing high if answer lies between current low and mid
    else if (mid * mid * mid > N)
      high = mid;

    // incrementing low if answer lies between mid and current high.
    else
      low = mid;
  }
  return Math.round(cuberoot * Math.pow(10, P)) / Math.pow(10, P);
}

The time complexity of the binary search approach is $O(log2(N) + log2(10P))$.


Liked the post?
Editor's Picks
0 COMMENT

Please login to view or add comment(s).