Nth root of BigInteger

Question

I'm using a BigInteger object. With normal ints or longs, I can use Math.pow(number, 1/nth root) to get the nth root. However, this will not work with a BigInteger. Is there a way I can do this?

I do not actually need the root, just to know if it is a perfect power. I'm using this to figure out if the given BigInteger is a perfect square/cube/etc.

Answer 1

Newton's method works perfectly well with integers; here we compute the largest number s for which s^k does not exceed n, assuming both k and n are positive:

function iroot(k, n)
    k1 := k - 1
    s := n + 1
    u := n
    while u < s
        s := u
        u := ((u * k1) + n // (u ** k1)) // k
    return s

For instance, iroot(4, 624) returns 4 and iroot(4, 625) returns 5. Then you can perform the exponentiation and check the result:

function perfectPower(k, n)
    return (k ** iroot(k, n)) == n

For instance, perfectPower(2, 625) and perfectPower(4, 625) are both true, but perfectPower(3, 625) is false.

I'll leave it to you to translate to Java BigInteger.

Answer 2

For starters you can use binary search it is easy to implement let:

• x be your bigint
• n the n-th power you want to check

so you want to check if there is y such that y^n=x and for starters assume x>=0 The algorithm is like this:

1. first compute y limit ymax

   I would use 2^(log2(x)/n) which is the number with (bits used for x)/n so ymax^n has the same amount of bits as x. So first count the bits of x and then divide it by n

   for (ymax=1,i=1;i<=x;i<<=1) ymax++; ymax=(ymax/n);
   

   now ymax is the number of bits the y need to be tested up to

2. bin search

    for(m=1<<ymax,y=0;m;m>>=1)
     {
     y|=m;
     if (integer_pow(y,n)>x) y^=m;
     }
    return (integer_pow(y,n)==x);
   

   the integer_pow(y,n) can be done by binary powering or with single for loop for small n

3. add handling the sign

   if (x<0) then n must be odd obviously and y<0 so if not return false else negate x and also the final y result.

[edit1] Here some simple C++ example:

bool is_root(DWORD &y,DWORD x,DWORD n) // y=x^(1/n) return true if perfect nth root
    {
    DWORD i,p,m; y=x;
    if (n==0) { y=0; return (x==0); }
    if (n==1) { y=x; return (x!=0); }
    for (i=1,m=1;m<x;i++,m<<=1); m=1<<(i/n); // compute the y limit
    for (y=0;m;m>>=1) // bin search through y
        {
        y|=m;
        for (p=y,i=1;i<n;i++) p*=y; // p=y^n
        if (p>x) y^=m; // this is xor not power!!!
        }
    for (p=y,i=1;i<n;i++) p*=y; // p=y^n
    return (p==x);
    }

so just convert the DWORD to your bigint datatype as you can see you need only basic arithmetic and bit operations like +,<,==,<<,>>,|,^ (the last is XOR not power)

There are also other possibilities to do this for some inspiration check this (and all sublinks in there):

• Power by squaring for negative exponents

So for example you can get even rid of the * operations (like I did in the 16T sqrt sublink presented in one of the sublinks (title: ... one cycle only)) Which is a huge speed up on bigints.

Answer 3

I solved the problem with this function I got from Newton's formula

public boolean perfectPower(BigDecimal a, double n){
    BigDecimal[] x = new BigDecimal[40];
    x[0] = BigDecimal.ONE;
    int digits = a.toString().length();
    System.out.println(digits);
    int roundTo = digits + 1;
    for(int k = 1; k < 40; k++){
        x[k] = (x[k - 1]
                .multiply(BigDecimal.valueOf((int)n - 1))
                .add(a
                        .divide(x[k - 1]
                        .pow((int)n - 1), new MathContext(roundTo, RoundingMode.HALF_EVEN))))
                .multiply(BigDecimal.valueOf(1/n));
    }
    String str = x[39].toString();
    return str.substring(str.indexOf(".") + 1, str.indexOf(".") + 6).equals("00000");
}

Answer 4

Factor the number and look at how many distinct factors there are. If there are is only one, it is a perfect n'th power, where n is the multiplicity of the factor. There may be more efficient methods but this is guaranteed to work.

Answer 5

Here's a BigInteger version for the Kth Root of N. I have also included a power function.

//      Input the N, Kth root. Returns N ^ 1/K

    public static BigInteger Ith_Root(BigInteger N, BigInteger K) {

        BigInteger K1 = K.subtract(BigInteger.ONE);
        BigInteger S  = N.add(BigInteger.ONE);
        BigInteger U  = N;
        while (U.compareTo(S)==-1) {
            S = U;
            U = (U.multiply(K1).add(N.divide(pow(U,K1)))).divide(K);
        }
        String str=""+N+"^1/"+K+"="+S;System.out.println(str);
       return S;   
    } 
    
public static BigInteger pow(BigInteger base, BigInteger exponent) {
      BigInteger result = BigInteger.ONE;
      while (exponent.signum() > 0) {
        if (exponent.testBit(0)) result = result.multiply(base);
        base = base.multiply(base);
        exponent = exponent.shiftRight(1);
      }
      return result;
    }