BigInteger 的第 N 个根

Question

我正在使用 BigInteger 对象。对于普通整数或长整数，我可以使用 Math.pow(number, 1/nth root) 来获得第 n 个根。但是，这不适用于 BigInteger。有没有办法做到这一点？

我其实并不需要根，只是想知道它是否是完美的力量。我用它来确定给定的 BigInteger 是否是一个完美的正方形/立方体/等。

Answer 1

牛顿法对整数非常有效；在这里，我们计算数量最多š针对小号^ķ不超过ñ，假设两个ķ和ñ是积极的：

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

例如，iroot(4, 624)返回 4 并iroot(4, 625)返回 5。然后您可以执行求幂并检查结果：

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

例如，perfectPower(2, 625)和perfectPower(4, 625)都是真的，但perfectPower(3, 625)都是假的。

我会让你把它翻译成 Java BigInteger。