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.
Newton's method works perfectly well with integers; here we compute the largest number s for which sk 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.