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.