Geek Answers Handbook

Nth root of BigInteger

I am 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 BigInteger. Is there a way I can do this?

I do not need a root, just to find out if it is an ideal force. I use this to find out if a given BigInteger is an ideal square / cube, etc.

+4
source share
4 answers

Newton's method works great with integers; here we calculate the largest number s for which s k does not exceed n, assuming that 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

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

+2

  • let:
  • x bigint
  • n n- ,
  • , y , y^n=x
  • x>=0

Algo:

1. y limit 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);
  • now ymax - , y

2. 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)
  • n

3.

  • if (x<0) n , y<0
  • , false
  • else negate x, y

[edit1] ++:

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

Number coefficient and see how many different factors there are. If there is only one, this is the perfect nth power, where n is the multiplicity of the factor. There may be more effective methods, but it is guaranteed.

0
source

More articles:


All Articles