BigInteger 的 N 次方根

Question

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

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

Answer 1

牛顿法对于整数来说效果非常好；这里我们计算最大数 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)

返回4，

iroot(4, 625)

返回5。然后您可以执行求幂并检查结果：

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

例如，

perfectPower(2, 625)

和

perfectPower(4, 625)

都是 true，但

perfectPower(3, 625)

是 false。

我将把它翻译成 Java BigInteger。

Answer 2

对于初学者，您可以使用二分搜索，它很容易实现let：

• x

  成为你的bigint

• n

  您要检查的n次方

所以你想检查是否存在

y

使得

y^n=x

对于初学者来说假设

x>=0

算法如下：

1. 首先计算

   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

   需要测试的位数

2. 垃圾箱搜索

    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

3. 添加处理标志

   如果

   (x<0)

   那么

   n

   显然必须是奇数并且

   y<0

   所以如果不返回 false，则否定

   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 而不是幂）

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

• 负指数的平方

因此，例如，您甚至可以摆脱

*

操作（就像我在其中一个子链接中呈现的 16T sqrt 子链接中所做的那样（标题：...仅一个周期）），这对 bigint 来说是一个巨大的加速。

Answer 3

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

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 4

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

Answer 5

这是 N 的第 K 个根的 BigInteger 版本。 我还添加了电源功能。

//      Input the N, Kth root. Returns N ^ 1/K

    public static BigInteger Ith_Root(BigInteger N, BigInteger K) {

        BigInteger K1 = K.subtract(BigInteger.ONE);
        BigInteger S  = N.add(BigInteger.ONE);
        BigInteger U  = N;
        while (U.compareTo(S)==-1) {
            S = U;
            U = (U.multiply(K1).add(N.divide(pow(U,K1)))).divide(K);
        }
        String str=""+N+"^1/"+K+"="+S;System.out.println(str);
       return S;   
    } 
    
public static BigInteger pow(BigInteger base, BigInteger exponent) {
      BigInteger result = BigInteger.ONE;
      while (exponent.signum() > 0) {
        if (exponent.testBit(0)) result = result.multiply(base);
        base = base.multiply(base);
        exponent = exponent.shiftRight(1);
      }
      return result;
    }

Answer 6

这是用于计算 BigInteger n 次方根的最佳 .net 库，带有 C# 源代码：https://www.nuget.org/packages/TheSquid.Numerics.Extensions