Find Cube Root of Number (without using cbrt())

Question

My code works perfectly for some floating value such as 125.5:

public class NewClass {

    public static void main(String[] args){
        Scanner Input = new Scanner(System.in);
        NewClass ob = new NewClass();
        double n = Input.nextDouble();
        double cbrt = ob.Cbrt(n);
        System.out.println(cbrt);
    }

    public  double GetSquareRoot(double n, double low, double high) {
        double cbrt = (low + high) / 2;
        
        if (cbrt*cbrt*cbrt > n)
            return GetSquareRoot(n, low, cbrt);
        if (cbrt*cbrt*cbrt < n)
            return GetSquareRoot(n, cbrt, high);
        return cbrt;
    }

    public double Cbrt(double n) {
        NewClass ob = new NewClass();
        return ob.GetSquareRoot(n, 0, n);
    }
}

It does not give correct answer when input is:

• 0.008
• or 0.125
• or 50
• or 100

Then I am getting java.lang.StackOverflowError.

When input is 125.5 or 125 or 8 it gives the correct solution.

Can someone help me?

Answer 1

The error is that this line:

return ob.GetSquareRoot(n, 0, n);

(which is, of course, misnamed) tries to find a solution between 0 and n. However, if 0 < n < 1, then n^1/3 > n, so you will never find a solution in the interval (0, n). You'll need to make a special case of this; for example, if 0 < n < 1, you can search the interval (n, 1) instead.

Also, using 0 and n as the bounds won't work for negative numbers, so if you want to make your method more complete and handle those cases, you'll need special cases for those too (probably different for -1 < n < 0 and n < -1).

MORE: After seeing your comment about StackOverflowError, it's occurred to me that you have an additional problem: that you're expecting an exact result. When you put in 0.008, the cube root is 0.2. However, neither 0.008 nor 0.2 can be represented exactly as a floating-point number. The consequence is that if you let cbrt = whatever value is closest to 0.2 that can be represented, then cbrt*cbrt*cbrt won't be exactly 0.008. It can't be exactly 0.008 anyway, since 0.008 can't be represented as a double; however, if n is whatever value is closest to 0.008, then it's likely that cbrt*cbrt*cbrt will not be exactly equal to n, due to roundoff errors. For a calculation like this, it's important that you not compare doubles for equality; instead, compare them using an "epsilon" value, or a margin of error. Thus, after

double cbrt = (low + high) / 2;

you should have something like

if (Math.abs(cbrt*cbrt*cbrt - n) < EPSILON)
    return cbrt;

where EPSILON is some small value such as 1E-10. (I've sometimes seen code where EPSILON is computed to be a relative value, i.e. abs(n * RELATIVE_EPSILON), instead of an absolute value.)

Another way to avoid StackOverflowError is to quit when low and high become really close, because by that point you're not going to gain much more accuracy, and you need to make sure you exit the algorithm even if the value of cbrt*cbrt*cbrt is a little bit off. Something like

if (high - low < EPSILON)
    return cbrt;

See also What's wrong with using == to compare floats in Java?.

Answer 2

//How about My Solution - Without Recursive

import java.util.Scanner;

public class CubeRoot {

public static void main(String[] args) {
    Scanner input = new Scanner(System.in);
    String str = input.next();
    Boolean negative = false;
    if (str.startsWith("-")) {
        str = str.substring(1);
        negative = true;
    }
    if (str.indexOf(".") > 0) {
        // find the poisition of '.'
        int pPos = str.length() - 1 - str.indexOf(".");
        String plainStr = (str.substring(0, str.indexOf('.')).concat(str.substring(str.indexOf('.') + 1)));
        StringBuffer cStr = new StringBuffer(cubeRoot(plainStr));

        if (cStr.toString().equalsIgnoreCase(plainStr))
            System.out.println("couldn't compute Cube Root for this :(");
        else {
            if (cStr.length() > pPos / 3) // devide 3 times to put the '.'
                cStr.insert(cStr.length() - pPos / 3, ".");
            else {
                int cStrLength = cStr.length();
                for (int i = 0; i <= pPos / 3 - cStrLength; i++)
                    cStr = new StringBuffer("0").append(cStr.toString());
                cStr.insert(cStr.length() - pPos / 3, ".");
            }
            String append = (negative) ? new String("-") : new String("");
            System.out.println(append + cStr.toString());
        }
    } else {
        System.out.println("Not a floating num");
    }
}

private static String cubeRoot(String d) {
    Long l = new Long(d);
    for (int i = 0; i < l; i++) {
        if (i * i * i == l) {
            return String.valueOf(i);
        }
    }
    return d;

}

}