Computing the nth root of p using BigDecimals

Question

I am currently trying to solve this problem as described here:

http://uva.onlinejudge.org/external/1/113.pdf

The plan was to implement a recursive function to derive the solution. Some of the code here comes from Rosetta code for determining the nth root.

// Power of Cryptography 113

import java.util.Scanner;
import java.math.BigDecimal;
import java.math.RoundingMode;

// k can be 10^9 
// n <= 200
// p <= 10^101

class crypto { 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()) {
            // Given two integers (n,p)
            // Find k such k^n = p
            int n = in.nextInt();
            BigDecimal p = in.nextBigDecimal();
            System.out.println(nthroot(n,p));
        }
    }

    public static BigDecimal nthroot(int n, BigDecimal A) {
        return nthroot(n, A, .001);
    }

    public static BigDecimal nthroot(int n, BigDecimal A, double p) {
        if(A.compareTo(BigDecimal.ZERO) < 0) return new BigDecimal(-1);
        // we handle only real positive numbers
        else if(A.equals(BigDecimal.ZERO)) {
            return BigDecimal.ZERO;
        }
        BigDecimal x_prev = A;
        BigDecimal x = A.divide(new BigDecimal(n));  // starting "guessed" value...
        BigDecimal y = x.subtract(x_prev);

        while(y.abs().compareTo(new BigDecimal(p)) > 0) {
            x_prev = x;
            BigDecimal temp = new BigDecimal(n-1.0);
            x = (x.multiply(temp).add(A).divide(x.pow(temp.intValue())).divide(new BigDecimal(n)));
        }
        return x;
    }
}

And here is the resulting error code:

Exception in thread "main" java.lang.ArithmeticException: Non-terminating decimal expansion; no exact representable decimal result.
at java.math.BigDecimal.divide(BigDecimal.java:1616)
at crypto.nthroot(crypto.java:38)
at crypto.nthroot(crypto.java:24)
at crypto.main(crypto.java:19)

Answer 1

That is expected if the resulting mathematical decimal number is non-terminating. The Javadocs for the 1-arg overload of divide state:

Throws:

ArithmeticException - if the exact quotient does not have a terminating decimal expansion

Use another overload of the divide method to specify a scale (a cutoff) (and a RoundingMode).

Answer 2

Anybody here for a working code snippet? Here we go:

public final class RootCalculus {

  private static final int SCALE = 10;
  private static final int ROUNDING_MODE = BigDecimal.ROUND_HALF_DOWN;

  public static BigDecimal nthRoot(final int n, final BigDecimal a) {
      return nthRoot(n, a, BigDecimal.valueOf(.1).movePointLeft(SCALE));
  }

  private static BigDecimal nthRoot(final int n, final BigDecimal a, final BigDecimal p) {
    if (a.compareTo(BigDecimal.ZERO) < 0) {
      throw new IllegalArgumentException("nth root can only be calculated for positive numbers");
    }
    if (a.equals(BigDecimal.ZERO)) {
        return BigDecimal.ZERO;
    }
    BigDecimal xPrev = a;
    BigDecimal x = a.divide(new BigDecimal(n), SCALE, ROUNDING_MODE);  // starting "guessed" value...
    while (x.subtract(xPrev).abs().compareTo(p) > 0) {
        xPrev = x;
        x = BigDecimal.valueOf(n - 1.0)
              .multiply(x)
              .add(a.divide(x.pow(n - 1), SCALE, ROUNDING_MODE))
              .divide(new BigDecimal(n), SCALE, ROUNDING_MODE);
    }
    return x;
  }

  private RootCalculus() {
  }
}

Just set SCALE to however precise you need the calculation to be.