CODEWITHSUNDEEP
javamathdoubledecimalnth-root
Sara Alaa Khodeir
Sara Alaa Khodeir

Reputation: 379

Calculating nth root in Java using power method

I was trying to get a cubic root in java using Math.pow(n, 1.0/3) but because it divides doubles, it doesn't return the exact answer. For example, with 125, this gives 4.9999999999. Is there a work-around for this? I know there is a cubic root function but I'd like to fix this so I can calculate higher roots.

I would not like to round because I want to know whether a number has an integer root by doing something like this: Math.pow(n, 1.0 / 3) % ((int) Math.pow(n, 1.0 / 3)).

Upvotes: 26

Views: 37429

Answers (10)

dimplex
dimplex

Reputation: 494

I'd go for implementing my own function to do this, possibly based on this method.

Upvotes: 1

Michel
Michel

Reputation: 339

I'm using this nth_root algorithm, which also provide the remainder :

   public static BigInteger[] sqrt(final BigInteger n) {
        final BigInteger[] res = {ZERO, n,};
        BigInteger a, b;
        assert (n.signum() > 0);
        a = ONE.shiftLeft(n.bitLength() & ~1);
        while (!a.equals(ZERO)) {
            b = res[0].add(a);
            res[0] = res[0].shiftRight(1);
            if (res[1].compareTo(b) >= 0) {
                res[1] = res[1].subtract(b);
                res[0] = res[0].add(a);
            }
            a = a.shiftRight(2);
        }
        return res;
    }

    public static BigInteger[] nth_root(BigInteger n, final int nth) {
        final BigInteger[] res;
        switch(nth){
                case 0 : res = new BigInteger[]{n.equals(ONE) ? ONE : ZERO, ZERO} ; break;
                case 1 : res = new BigInteger[]{n, ZERO}; break;
                case 2 : res = sqrt(n); break;
                default:
                    int sign = n.signum() ;
                    n = n.abs();
                        res = new BigInteger[]{n.shiftLeft((n.bitLength() + nth - 1) / nth), n};
                        while(res[1].compareTo(res[0])<0) {
                            res[0] = res[1];
                            res[1] = BigInteger.valueOf(nth-1).multiply(res[1]).add(n.divide(res[1].pow(nth - 1))).divide(BigInteger.valueOf(nth));
                        }
                        res[1] = res[0].pow(nth);
                        res[1] = n.subtract(res[1]);
                        if (sign < 0 && (nth & 1) == 1) {
                            res[0] = res[0].negate();
                            res[1] = res[1].negate();
                        } else assert (sign > 0);
            }
            return res ;
        }
    }

Upvotes: 0

Vpn_talent
Vpn_talent

Reputation: 1436

Find nth root Using binary search method. Here is the way to find nth root with any precision according to your requirements.

import java.util.Scanner;

public class FindRoot {

    public static void main(String[] args) {
        try (Scanner scanner = new Scanner(System.in)) {
            int testCase = scanner.nextInt();
            while (testCase-- > 0) {
                double number = scanner.nextDouble();
                int root = scanner.nextInt();
                double precision = scanner.nextDouble();
                double result = findRoot(number, root, precision);
                System.out.println(result);
            }
        }
    }

    private static double findRoot(double number, int root, double precision) {
        double start = 0;
        double end = number / 2;
        double mid = end;
        while (true) {
            if (precision >= diff(number, mid, root)) {
                return mid;
            }
            if (pow(mid, root) > number) {
                end = mid;
            } else {
                start = mid;
            }
            mid = (start + end) / 2;
        }
    }

    private static double diff(double number, double mid, int n) {
        double power = pow(mid, n);
        return number > power ? number - power : power - number;
    }

    private static double pow(double number, int pow) {
        double result = number;
        while (pow-- > 1) {
            result *= number;
        }
        return result;
    }
}

Upvotes: 0

Vpn_talent
Vpn_talent

Reputation: 1436

Here is the solution without using Java's Math.pow function. It will give you nearly nth root

public class NthRoot {

public static void main(String[] args) {
    try (Scanner scanner = new Scanner(System.in)) {
        int testcases = scanner.nextInt();
        while (testcases-- > 0) {
            int root = scanner.nextInt();
            int number = scanner.nextInt();
            double rootValue = compute(number, root) * 1000.0 / 1000.0;
            System.out.println((int) rootValue);
        }
    } catch (Exception e) {
        e.printStackTrace();
    }
}

private static double compute(int number, int root) {
    double xPre = Math.random() % 10;
    double error = 0.0000001;
    double delX = 2147483647;
    double current = 0.0;

    while (delX > error) {
        current = ((root - 1.0) * xPre + (double) number / Math.pow(xPre, root - 1)) / (double) root;
        delX = Math.abs(current - xPre);
        xPre = current;
    }
    return current;
}

Upvotes: 2

Grigoris Dimopoulos
Grigoris Dimopoulos

Reputation: 124

You can use some tricks come from mathematics field, to havemore accuracy. Like this one x^(1/n) = e^(lnx/n).

Check the implementation here: https://www.baeldung.com/java-nth-root

Upvotes: 1

user3088035
user3088035

Reputation:

It's a pretty ugly hack, but you could reach a few of them through indenting.

System.out.println(Math.sqrt(Math.sqrt(256)));
    System.out.println(Math.pow(4, 4));
    System.out.println(Math.pow(4, 9));
    System.out.println(Math.cbrt(Math.cbrt(262144)));
Result:
4.0
256.0
262144.0 
4.0

Which will give you every n^3th cube and every n^2th root.

Upvotes: 0

Avneesh Singh
Avneesh Singh

Reputation: 1

Well this is a good option to choose in this situation. You can rely on this-

   System.out.println("     ");
   System.out.println("     Enter a base and then nth root");
   while(true)
   {
       a=Double.parseDouble(br.readLine());
       b=Double.parseDouble(br.readLine());
       double negodd=-(Math.pow((Math.abs(a)),(1.0/b)));
       double poseve=Math.pow(a,(1.0/b));
       double posodd=Math.pow(a,(1.0/b));
       if(a<0 && b%2==0)
       {
           String io="\u03AF";
           double negeve=Math.pow((Math.abs(a)),(1.0/b));
           System.out.println("     Root is imaginary and value= "+negeve+" "+io);
       }
       else if(a<0 && b%2==1)
       System.out.println("     Value= "+negodd);
       else if(a>0 && b%2==0)
       System.out.println("     Value= "+poseve);
       else if(a>0 && b%2==1)
       System.out.println("     Value= "+posodd);
       System.out.println("     ");
       System.out.print("     Enter '0' to come back or press any number to continue- ");
       con=Integer.parseInt(br.readLine());
       if(con==0)
       break;
       else
       {
           System.out.println("     Enter a base and then nth root");
           continue;
       }
    }

Upvotes: 0

Paul Boddington
Paul Boddington

Reputation: 37645

I wrote this method to compute floor(x^(1/n)) where x is a non-negative BigInteger and n is a positive integer. It was a while ago now so I can't explain why it works, but I'm reasonably confident that when I wrote it I was happy that it's guaranteed to give the correct answer reasonably quickly.

To see if x is an exact n-th power you can check if the result raised to the power n gives you exactly x back again.

public static BigInteger floorOfNthRoot(BigInteger x, int n) {
    int sign = x.signum();
    if (n <= 0 || (sign < 0))
        throw new IllegalArgumentException();
    if (sign == 0)
        return BigInteger.ZERO;
    if (n == 1)
        return x;
    BigInteger a;
    BigInteger bigN = BigInteger.valueOf(n);
    BigInteger bigNMinusOne = BigInteger.valueOf(n - 1);
    BigInteger b = BigInteger.ZERO.setBit(1 + x.bitLength() / n);
    do {
        a = b;
        b = a.multiply(bigNMinusOne).add(x.divide(a.pow(n - 1))).divide(bigN);
    } while (b.compareTo(a) == -1);
    return a;
}

To use it:

System.out.println(floorOfNthRoot(new BigInteger("125"), 3));

Edit Having read the comments above I now remember that this is the Newton-Raphson method for n-th roots. The Newton-Raphson method has quadratic convergence (which in everyday language means it's fast). You can try it on numbers which have dozens of digits and you should get the answer in a fraction of a second.

You can adapt the method to work with other number types, but double and BigDecimal are in my view not suited for this kind of thing.

Upvotes: 1

Tunaki
Tunaki

Reputation: 137064

Since it is not possible to have arbitrary-precision calculus with double, you have three choices:

  1. Define a precision for which you decide whether a double value is an integer or not.
  2. Test whether the rounded value of the double you have is a correct result.
  3. Do calculus on a BigDecimal object, which supports arbitrary-precision double values.

Option 1

private static boolean isNthRoot(int value, int n, double precision) {
    double a = Math.pow(value, 1.0 / n);
    return Math.abs(a - Math.round(a)) < precision; // if a and round(a) are "close enough" then we're good
}

The problem with this approach is how to define "close enough". This is a subjective question and it depends on your requirements.

Option 2

private static boolean isNthRoot(int value, int n) {
    double a = Math.pow(value, 1.0 / n);
    return Math.pow(Math.round(a), n) == value;
}

The advantage of this method is that there is no need to define a precision. However, we need to perform another pow operation so this will affect performance.

Option 3

There is no built-in method to calculate a double power of a BigDecimal. This question will give you insight on how to do it.

Upvotes: 11

Manos Nikolaidis
Manos Nikolaidis

Reputation: 22214

The Math.round function will round to the nearest long value that can be stored to a double. You could compare the 2 results to see if the number has an integer cubic root.

double dres = Math.pow(125, 1.0 / 3.0);
double ires = Math.round(dres);
double diff = Math.abs(dres - ires);
if (diff < Math.ulp(10.0)) {
    // has cubic root
}

If that's inadequate you can try implementing this algorithm and stop early if the result doesn't seem to be an integer.

Upvotes: 6

Related Questions