大整数的N次方根

Question

大整数的N次方根

javamathbigintegersquare-root

7

我正在使用BigInteger对象。对于普通的int或long，我可以使用Math.pow(number, 1/nth root)来获取nth根。然而，这在BigInteger上不起作用。有没有办法可以做到这一点？

我实际上并不需要根，只需要知道它是否是一个完全幂。我正在使用此方法来确定给定的BigInteger是否是完全平方/立方等。

- James McDowell

2

相关：Guava的BigIntegerMath.sqrt。 - Louis Wasserman

有一个类似的问题：https://dev59.com/LW855IYBdhLWcg3wViot - hoyah_hayoh

谢谢Louis。这正是我需要的sqrt部分。我还需要确定它是否也是一个立方体。 - James McDowell

http://www.hackersdelight.org/hdcodetxt/icbrt.c.txt 包含整数立方根的算法。我会将其翻译成 BigInteger。 - Louis Wasserman

1

牛顿迭代法求解n次方根在这里：https://en.wikipedia.org/wiki/Nth_root_algorithm - Edward Doolittle

显示剩余2条评论

5个回答

2

首先，你可以使用二分查找，它很容易实现，让：

x为您的大整数
n是您想要检查的n次方

所以你想检查是否存在y使得y^n=x，并且首先假设x>=0。算法如下：

first compute y limit ymax

I would use 2^(log2(x)/n) which is the number with (bits used for x)/n so ymax^n has the same amount of bits as x. So first count the bits of x and then divide it by n
```
for (ymax=1,i=1;i<=x;i<<=1) ymax++; ymax=(ymax/n);
```
now ymax is the number of bits the y need to be tested up to

bin search

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

the integer_pow(y,n) can be done by binary powering or with single for loop for small n

add handling the sign

if (x<0) then n must be odd obviously and y<0 so if not return false else negate x and also the final y result.

[编辑1]这里是一个简单的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转换为您的大整数数据类型，正如您所看到的，您只需要基本算术和位运算符，如

+，<，==，<<，>>，|，^ （最后一个是XOR而不是幂）。
还有其他可能性可以做到这一点，例如，可以在此处检查所有子链接以获得一些灵感：


负指数平方幂


因此，例如，您甚至可以摆脱*操作（就像我在其中一个子链接中介绍的16T sqrt子链接中所做的那样（标题：...仅一个周期）），这对于大数据类型来说是巨大的速度提升。

- Spektre

0

对该数字进行因数分解，并查看有多少个不同的因子。如果只有一个因子，则它是一个完全的n次幂，其中n是该因子的重复次数。可能存在更有效的方法，但这种方法保证可行。

- Robert Dodier

1

但是因式分解非常昂贵，而且如果数字足够大，则根本无法进行，因此不能保证其有效性。 - Alexander Kjäll

0

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

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

- James McDowell

我不知道。你正在寻找一个确切的答案，但我不清楚这种方法是否能给你一个确切的答案。最终测试是小数点后的前5位数字都是零吗？我猜很容易构造一个例子来证明这种方法会失败...嗯，试试用这种方法求10^12 + 1的四次方根。 - Robert Dodier

您可以通过迭代来解决这个问题，直到x[i]和x[i+1]之间的差小于0.5，然后测试floor(x[i+1])或ceiling(x[i+1])是否是一个完美的N次幂。通过将其提高到N次幂来实现。 - Stephen C

0

这里是计算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;
    }

- Anthony Overmars

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user448810 · Accepted Answer

牛顿法在整数中可以完美地工作；在这里，我们计算最大的数字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)都为真，但perfectPower(3, 625)为假。

我将让您将其翻译为Java BigInteger。