javamathbigintegersquare-root

Nth root of BigInteger


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.


Solution

  • 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.