BigInteger 的 N 次方根

Question

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

我其实并不需要root，只是想知道它是否是一个完美的力量。我用它来确定给定的 BigInteger 是否是完美的 square/cube/etc.

Answer 1

我用这个从牛顿公式得到的函数解决了问题

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 2

对数字进行因式分解，看看有多少不同的因数。如果只有一个，则它是完美的 n 次方，其中 n 是因子的重数。可能有更有效的方法，但这保证有效。

Answer 3

初学者可以使用二分查找实现起来很容易让:

x 成为你的 bigint
n您要检查的n-th功率

所以你想检查是否有 y 使得 y^n=x 并且首先假设 x>=0 算法是这样的：

首先计算y极限ymax

我会使用 2^(log2(x)/n)，这是带有 (bits used for x)/n 的数字，因此 ymax^n 与 x 具有相同的位数。所以先数一下x的位数然后除以n
```
for (ymax=1,i=1;i<=x;i<<=1) ymax++; ymax=(ymax/n);
```
现在 ymax 是 y 需要测试的位数

bin搜索

 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);

integer_pow(y,n) 可以通过二进制供电或使用单个 for 循环实现小 n

添加处理标志

if (x<0) then n 显然必须是奇数并且 y<0 所以如果不是 return false else 否定 x 以及最后的 y结果。

[edit1] 这里有一些简单的 C++ 示例：

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);
    }

所以只需将 DWORD 转换为您的 bigint 数据类型，如您所见，您只需要基本的算术和位运算，例如 +,<,==,<<,>>,|,^（最后一个是 XOR 而不是幂）

还有其他的可能性可以这样做以获得一些灵感，检查这个（以及那里的所有子链接）：

Power by squaring for negative exponents

因此，例如，您甚至可以摆脱 * 操作（就像我在其中一个子链接中显示的 16T sqrt 子链接中所做的那样（标题：...仅一个循环））这是一个大大加快了 bigints 的速度。

Answer 4

牛顿法非常适用于整数；这里我们计算最大数 s 其中 s^k 不超过 n ，假设 k 和 n 都是正数：

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) returns 4 和 iroot(4, 625) returns 5。然后你可以进行取幂并查看结果：

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

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

我会留给你翻译成 Java BigInteger。

BigInteger 的 N 次方根

Nth root of BigInteger

java

math

biginteger

square-root